Detecting if two strings are anagrams
As @Graipher suggested, why bother do this yourself when Python's builtins could give you the answer on a golden plate?

from collections import Counter 


def are_anagrams(str1, str2):
    """Return True if str1 and str2 are anagrams and False otherwise.""" 
    return Counter(str1) == Counter(str2)


Some examples:


are_anagrams('123', '321')
True
are_anagrams('', '')
True
are_anagrams('aabbcc', 'bacac')
False



And that's it. Furthermore it's \$O(n)\$ as you wanted.

And don't think it's something hard to grasp underneath, it's basically just a dictionary with its items as keys and counts as values.



Regarding your code, there are a few style issues that I'd like to point out:


avoid useless/obvious comments like # automatic failure
use 4 spaces per indentation level. (always - not two, not one, not 10. Always 4)
there should be one space after the comma (def are_anagrams(s1, s2):)
don't forget the dot at the end of the docstring (OCD, sorry)
you should always put a space after #


Instead of doing this:

for key in d:
    if d[key]:
        ...


You can do (look also for iteritems() for other python versions):

for key, value in d.items():
    if value:
        ...


To iterate over a string's chars it's recommended to use Python's builtin enumerate (instead of that while) like this:

for index, char in enumerate('test'):
    print('char: {}; index: {}'.format(char, index))

char: t; index: 0
char: e; index: 1
char: s; index: 2
char: t; index: 3