Determine If Two Strings Are Anagrams Efficiently
Company: Google
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Backend service needs to verify whether two user-provided strings are anagrams for text-matching features.
##### Question
Implement a Python function is_anagram(s1, s
2) that returns True if the two input strings are anagrams of each other, otherwise False. Explain time and space complexity.
##### Hints
Normalize case; compare sorted strings or use a character-count hash map.
Quick Answer: This question evaluates proficiency in string manipulation, algorithmic efficiency, and time/space complexity analysis within the Coding & Algorithms domain for data scientist roles.
Given two strings s1 and s2, return True if they are anagrams of each other when compared case-insensitively, otherwise return False. Treat every character, including spaces and punctuation, as significant after converting both strings to lowercase.
Constraints
- 0 <= len(s1), len(s2) <= 200000
- Characters are printable ASCII (code points 32 to 126).
- Comparison is case-insensitive; all characters (including spaces and punctuation) are significant.
- Expected time complexity: O(n).
Solution
def is_anagram(s1: str, s2: str) -> bool:
# Normalize case
s1 = s1.lower()
s2 = s2.lower()
# Quick length check
if len(s1) != len(s2):
return False
counts = {}
for ch in s1:
counts[ch] = counts.get(ch, 0) + 1
for ch in s2:
cnt = counts.get(ch)
if cnt is None:
return False
if cnt == 1:
del counts[ch]
else:
counts[ch] = cnt - 1
return not counts
Explanation
Convert both strings to lowercase, then compare their character frequency distributions using a dictionary. First increment counts for characters in s1, then decrement for characters in s2. If any character is missing or over-decremented, return False. If all counts balance to zero, the strings are anagrams.
Time complexity: O(n). Space complexity: O(1) with fixed ASCII alphabet; O(k) otherwise.
Hints
- Normalize both strings to lowercase.
- If lengths differ after normalization, return False immediately.
- Use a hash map (dictionary) to count characters in s1 and decrement with s2.
- Alternatively, compare sorted lowercase strings (O(n log n)).
- With ASCII, an array of size 128 can store counts.