Using Arrays as Containers

Valid Anagram

Two strings are anagrams of each other if they have the same character set (and frequency of characters) and the same length. For example strings "bacdc" and "dcbac" are anagrams, while strings "bacdc" and "dcbad" are not.

Given two strings s and t, write a function to check if they are anagrams of each other.

You can assume that s and t only consist of lowercase latin letter.

Solution:

To examine if t is a rearrangement of s, we can count occurrences of each letter in the two strings and compare them. Since both s and t contain only lowercase latin letters, a simple counter table of size 26 will suffice.

Do we need two counter tables for comparison? Actually no, because we could first increment the counter for s, then decrement the counter for t, and finally check if every counter equals zero.

def is_anagram(s, t):
    counter = [0] * 26
    for s_char in s:
        counter[ord(s_char)-ord('a')] += 1
    for t_char in t:
        counter[ord(t_char)-ord('a')] -= 1
    return not any(counter)

Implementation Details:

If you don't know what ord does in Python, read this.

The last line not any(counter) returns True if and only if each entry in counter equals zero. Can we replace return not any(counter) with return sum(counter) == 0? When will it fail?

Complexity:

Time: O(n)
Space: O(1)

Can we do better?

While the worst case run time cannot be further optimized, we can add some simple checks in our code so it "fails fast":

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    counter = [0] * 26
    for s_char in s:
        counter[ord(s_char)-ord('a')] += 1
    for t_char in t:
        counter[ord(t_char)-ord('a')] -= 1
        if counter[ord(t_char)-ord('a')] < 0:
            return False
    return True

Note that when s and t have the same length, no counter being negative implies every counter equals zero.

Follow-up Questions:

Make it Anagram

Given two strings (they can be of same or different length), find the minimum number of character deletions required to make two strings anagrams. Any characters can be deleted from any of the strings.

You can assume that the two strings will only consist of lowercase latin letter.

For example, given two strings "cde" and "abc", the result should be 4. We need to delete 4 characters to make both strings anagram: 'd' and 'e' from the first string and 'b' and 'a' from the second string.

Solution:

def min_deletions(string1, string2):
    array1, array2 = [0] * 26, [0] * 26
    for char1 in string1:
        array1[ord(char1)-ord('a')] += 1
    for char2 in string2:
        array2[ord(char2)-ord('a')] += 1
    common = sum(min(a, b) for a, b in zip(array1, array2))
    return len(string1) + len(string2) - 2*common

Extra Long Factorials

You are given an integer N. Print the factorial of this number.

Note: Factorials of N > 20 can't be stored even in a 64−bit long long variable

Solution:

Exercises:

1.