Big O Practice: Valid Anagram

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

Variables

• n - length of either input string (they must match)

Explanation

Two linear passes over the strings - **O(n)** time. The counter array is fixed at 26 slots regardless of input, so space is **O(1)**. If the alphabet were unbounded the answer would shift to O(n) space.

More Big O practice problems · Today's daily problem