String Permutations

Up next is checking whether one string is a permutation of another string. When I originally wrote my solution I was thinking the question was asking to find a permutation which is also a substring of the other string. My solution for that problem looks like:

from collections import Counter
def isPermutation(s1, s2):
    c = Counter(s1)
    for n in s2:
        c[n] -= 1

    for v in c.itervalues():
        if v < 0:
            return False

    return True

This again makes use of a Counter from collections. I think the only real takeaway here is you should definitely clarify with the interviewer up front what’s expected by the question. In this case it would have been better to have just written:

def isPermutation(s1, s2):
    c1 = Counter(s1)
    c2 = Counter(s2)
    return c1 == c2

Which is really just an exercise in comparing two dictionaries. Behind the scenes python is going to take O(n) to construct the two counters, but it’s unclear to me exactly how it will compare them against each other. My suspicion would be that it would compare the keys of the two dictionaries in alphabetical order, which would mean n*log(n) for runtime complexity, but you could have constructed the counter as an array of 26 or so integers for all of the lowercase characters in the string, and then compared the two arrays. For that case you’re still in O(n).

The other solution the book mentions is to sort the arrays themselves and compare, which would look something like:

def isPermutation(s1, s2):
    return sorted(s1) == sorted(s2)

That saves you the extra step of using the Counter, and you end up in n*log(n) land again thanks to the timsort. There’s also the temporary storage for holding the two ordered strings which gets chucked away once the function returns.