Valid Anagram

Today, I’m tackling the Valid Anagram problem, a classic that not only tests basic string manipulation but also real‑world pattern matching. This problem is a great warm‑up because it uses simple techniques that have many applications!

Problem Statement

Given two strings s and t, determine if t is an anagram of s. An anagram is formed by rearranging the letters of another string, using every letter exactly once. The solution should return True if t is an anagram of s, and False otherwise.

1. Clarify Requirements Before Jumping Into Code

I need to confirm a couple of details first. I assume both strings consist of lowercase English letters. If the lengths differ, the answer is immediately False. I’ll need to decide if I can change the strings or not; the question implies I shouldn’t need to modify them. Finally, I confirm that I'm comparing overall frequency of each letter, not position or order.

2. Identify the Category of the Question

This is a string manipulation problem that involves counting frequencies, an ideal fit for a hash table or fixed‑size array approach. It belongs to the categories of hashing and frequency counting, which I often see when checking if two data collections are equivalent regardless of order.

3. Consider a Brute‑Force Approach to Understand the Problem

A straightforward, if not optimal, solution might be to generate all permutations of s and check if t is one of those. However, this method would be extremely inefficient with factorial time complexity, making it impractical for even moderately sized strings.

I could also go letter by letter, comparing every character in one string against all the strings in the other. This is O(n^2) time which is also inefficient. But this idea of comparing letters in each string is on the right track, I just need a data structure that will help me look up what characters I've seen before in constant time!

4. Brainstorm More Solutions

A better method is to count the characters in each string and compare their frequency. I could do this by sorting both strings and comparing if they are identical, or by using a hash map (or fixed‑size array) to tally character counts and then compare these counts. Sorting will give me O(n log n) time, while the hash table method can achieve O(n) time complexity.

5. Discuss Trade‑Offs Between Your Solutions

• Brute‑Force (Permutation):

  • Time Complexity: O(n!)

  • Space Complexity: O(n)

  • Pros: Conceptually simple.

  • Cons: Not feasible for practical input sizes.

• Sorting:

  • Time Complexity: O(n log n)

  • Space Complexity: Depends on sorting algorithm; can be O(1) if in-place.

  • Pros: Easy to implement with built‑ins; clear logic.

  • Cons: Not optimal if an O(n) solution exists.

• Hash Table / Fixed‑Size Array:

  • Time Complexity: O(n)

  • Space Complexity: O(1) if using a fixed‑size array for 26 letters.

  • Pros: Fast and efficient; optimal for this problem.

  • Cons: Slightly more code required for counting.

The hash table solution is ideal here.

6. Write Pseudocode to Structure Your Thoughts

function isAnagram(s, t):
    if length(s) ≠ length(t):
        return False

    initialize count array or hash map for letters

    for each character c in s:
        increment count[c]

    for each character c in t:
        decrement count[c]
        if count[c] < 0:
            return False

    return True

7. Consider Edge Cases

• Two empty strings: both should return True.

• One empty string and one non‑empty string: return False.

• Strings of different lengths: return False immediately.

• Identical strings: return True.

• Strings with repeated characters, ensuring counts match exactly.

8. Write Full Code Syntax

def is_anagram(s, t):
    # If lengths differ, cannot be anagrams
    if len(s) != len(t):
        return False

    # Using a fixed-size list for 26 lowercase letters
    count = [0] * 26
    # Process first string
    for char in s:
        count[ord(char) - ord('a')] += 1
    
    # Process second string
    for char in t:
        count[ord(char) - ord('a')] -= 1
        if count[ord(char) - ord('a')] < 0:
            return False
    
    # If all counts are zero, strings are anagrams
    return True

9. Test Your Code

# Test Case 1: Simple anagram
s1 = "anagram"
t1 = "nagaram"
assert is_anagram(s1, t1) == True

# Test Case 2: Not an anagram
s2 = "rat"
t2 = "car"
assert is_anagram(s2, t2) == False

# Test Case 3: Empty strings
s3 = ""
t3 = ""
assert is_anagram(s3, t3) == True

# Test Case 4: Different lengths
s4 = "hello"
t4 = "billion"
assert is_anagram(s4, t4) == False

# Test Case 5: Same letters but different frequency
s5 = "aabbcc"
t5 = "abcabc"
assert is_anagram(s5, t5) == True

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

• When checking for anagrams or similar problems, think in terms of character counts and frequency matching.

• If input sizes allow, always check the lengths first as a quick fail condition.

• Hash table or fixed-size array techniques can reduce time complexity to O(n) for counting problems.

• Sorting is a viable alternative, but in this case, it won’t beat a direct frequency count in terms of efficiency.

• Always test for edge cases, particularly with empty strings or mismatched string lengths.

• Clear communication about your thought process is essential; it shows you’re methodical and efficient in designing solutions.

  
  

Happy coding!