DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Valid Anagram

easyArrays and hashing

Problem statement

You are given two strings s and t made of lowercase English letters. Return true if t uses exactly the same letters as s, each the same number of times, just possibly in a different order. Otherwise return false.

Examples

Example 1

Input: s = "listen", t = "silent"

Output: true

Explanation: Both contain one each of e, i, l, n, s, t.

Example 2

Input: s = "deploy", t = "depots"

Output: false

Explanation: s has l and y, t has t and s instead.

Hints

Approach

Count letters instead of sorting them. Add one for every letter of s, subtract one for every letter of t. If the strings are anagrams, every counter ends at zero.

  1. If the lengths differ, return false.
  2. Make 26 counters, one per letter.
  3. Increment for each letter in s.
  4. Decrement for each letter in t. If a counter goes below zero, t has more of that letter than s, so return false.
  5. Return true.

Because the lengths are equal, no counter can stay positive without another going negative, so step 4 catches every mismatch. The 26-slot array is fixed size, so the extra space is O(1).

ComplexityTime O(n)Space O(1)
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
counts = [0] * 26
for ch in s:
counts[ord(ch) - ord("a")] += 1
for ch in t:
i = ord(ch) - ord("a")
counts[i] -= 1
if counts[i] < 0:
return False
return True

Follow-up questions

  • Group a whole list of words into sets of anagrams.
  • Find every position in a long string where an anagram of a short string starts.

Frequently asked questions

The fixed 26-slot array no longer fits. Use a hash map from character to count instead (Counter in Python, HashMap<Character, Integer> in Java). The time stays O(n), and the space grows with the number of distinct characters.

Yes, it is O(n) and clear. Be ready to explain what it does underneath, because the interviewer usually wants to see the counting idea.

Comparing two collections while ignoring order is common: checking that two hosts have the same set of installed packages, or that a new config has the same keys as the old one. Counting by key is the same technique.