← DSA practice

Valid Anagram

EasyStrings · CountingO(n) time · O(1) space (26 letters)

The problem

Given two strings, return true if one is an anagram of the other — same letters, same counts, any order.

"listen", "silent"  →  true
"rat", "car"        →  false
Stuck? Open one hint

Sorting works and is easy to say. Can you do it without sorting?

Show the worked solution

Sorting both and comparing is O(n log n) and perfectly acceptable as a first answer — say it, then improve it.

Counting is O(n): one array of 26 counts, add for the first string, subtract for the second. If every count ends at zero, it is an anagram. Different lengths can be rejected immediately.

Mention the follow-up before they ask: for Unicode, swap the 26-slot array for a HashMap of code points.

fun isAnagram(s: String, t: String): Boolean {
    if (s.length != t.length) return false
    val counts = IntArray(26)
    for (i in s.indices) {
        counts[s[i] - 'a']++
        counts[t[i] - 'a']--
    }
    return counts.all { it == 0 }
}

O(n) time · O(1) space (26 letters)