Lecture: Solving the 'Valid Anagram' Problem

Introduction

• Objective: Determine if two strings s and t are anagrams.
• Definition: An anagram means using the exact characters of s to create t.

Example Scenarios

• Example 1:
  • s = "anagram", t = "nagaram"
  • Both strings have the same characters with the same frequency.
  • Result: True
• Example 2:
  • s = "rat", t = "car"
  • Both strings have the same length but different characters.
  • Result: False

Solution 1: Using Hash Maps

• Approach:
  • Create two hash maps for s and t to count the occurrences of each character.
  • Compare the two hash maps.
• Steps:
  1. Ensure strings are of the same length: If not, return false.
  2. Count characters:
     • Iterate over both strings simultaneously.
     • Increment counts in respective hash maps.
  3. Compare hash maps:
     • Iterate through keys in one hash map and verify counts in the other.
     • Use the get method to avoid key errors with a default value of 0.
• Time Complexity: O(s + t)
• Space Complexity: O(s + t)
• Python Example Code:

  def is_anagram(s, t):
      if len(s) != len(t):
          return False
      count_s, count_t = {}, {}
      for i in range(len(s)):
          count_s[s[i]] = count_s.get(s[i], 0) + 1
          count_t[t[i]] = count_t.get(t[i], 0) + 1
      for char in count_s:
          if count_s[char] != count_t.get(char, 0):
              return False
      return True
  

• Alternative using Python's Counter:

  from collections import Counter
  def is_anagram(s, t):
      return Counter(s) == Counter(t)
  

Solution 2: Sorting

• Approach:
  • Sort both strings and compare them.
• Steps:
  1. Ensure strings are of the same length: If not, return false.
  2. Sort both strings.
  3. Compare sorted strings.
• Time Complexity: O(n log n) for sorting
• Space Complexity: Varies; often O(1) if in-place, but typically considered O(n)
• Python Example Code:

  def is_anagram(s, t):
      return sorted(s) == sorted(t)
  

Conclusion

• Both solutions are effective, but they have different trade-offs in terms of time and space complexity.
• Sorting-based solution is straightforward but less efficient.
• Hash map-based solution is more efficient but uses extra space.
• Interview Tip: Always discuss time/space complexities and edge cases with interviewers.