Valid Anagram is the first string problem in the Tekraze DSA series, and it teaches a trick you will reuse again and again: counting characters. Welcome to Day 4. In Day 1 we used a hash map, in Day 2 a single pass with a running minimum, and in DSA Series Day 3: Contains Duplicate in Java, Python and Rust. Today we move to strings.
Also Read: Day 1: Two Sum shows where the hash map idea first appears in this series.
What is the Valid Anagram problem?
You get two strings, s and t. Return true if t is an anagram of s. That means it uses exactly the same letters the same number of times, just in a different order. Assume both strings contain only lowercase English letters.
text
Input: s = "anagram", t = "nagaram" Output: true Input: s = "rat", t = "car" Output: false Why: t has a c and no t
This is LeetCode 242, a common warm-up question in coding interviews.
How should you think about the Valid Anagram problem?
Think of two bags of Scrabble tiles. They make anagrams only if both bags hold the same tiles. You don’t care about order, only about how many of each letter you have.
So the question becomes simple. Count the letters in the first string, take away the letters in the second, and check that every count ends at zero.
What does the brute force solution look like?
The most obvious idea is to sort both strings and compare them. Two anagrams always become the same string once sorted.
python
def is_anagram_sort(s, t):
return sorted(s) == sorted(t)
Time is O(n log n) because of the sort. Space is O(n) for the sorted copies in most languages. It is short and correct, and a fine first answer, but we can skip the sort completely.
An even slower idea is to take each letter of s and search for it in t, removing it when found. That is O(n²), so mention it only to show why counting is better.
How do you get the optimal O(n) Valid Anagram solution?
Keep a count for each letter. Walk both strings together, add one for the letter in s and subtract one for the letter in t. If the lengths differ, return false right away. At the end, every count must be zero.
Time is O(n): one pass through the strings plus a check of 26 counters. Space is O(1), because the array always has 26 slots no matter how long the strings are. Not sure why a fixed-size array counts as constant space? Read our Big O helper post on time and space complexity.
Java solution for Valid Anagram
java
public class Solution {
public static boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
public static void main(String[] args) {
String[][] tests = {{"anagram", "nagaram"}, {"rat", "car"}, {"", ""}, {"a", "ab"}, {"listen", "silent"}};
boolean[] expected = {true, false, true, false, true};
for (int i = 0; i < tests.length; i++) {
boolean got = isAnagram(tests[i][0], tests[i][1]);
System.out.println((got == expected[i] ? "PASS" : "FAIL") + " " + tests[i][0] + "," + tests[i][1] + " -> " + got);
}
}
}
Python solution for Valid Anagram
python
def is_anagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = {}
for a, b in zip(s, t):
count[a] = count.get(a, 0) + 1
count[b] = count.get(b, 0) - 1
return all(v == 0 for v in count.values())
if __name__ == "__main__":
tests = [("anagram", "nagaram", True), ("rat", "car", False), ("", "", True),
("a", "ab", False), ("listen", "silent", True)]
for s, t, want in tests:
got = is_anagram(s, t)
print("PASS" if got == want else "FAIL", s, t, "->", got)
Rust solution for Valid Anagram
rust
fn is_anagram(s: &str, t: &str) -> bool {
if s.len() != t.len() {
return false;
}
let mut count = [0i32; 26];
for (a, b) in s.bytes().zip(t.bytes()) {
count[(a - b'a') as usize] += 1;
count[(b - b'a') as usize] -= 1;
}
count.iter().all(|&c| c == 0)
}
fn main() {
let tests = [("anagram", "nagaram", true), ("rat", "car", false), ("", "", true),
("a", "ab", false), ("listen", "silent", true)];
for (s, t, want) in tests {
let got = is_anagram(s, t);
println!("{} {} {} -> {}", if got == want { "PASS" } else { "FAIL" }, s, t, got);
}
}
Java and Rust use a fixed array of 26 integers, which is the fastest option for lowercase letters. The Python version uses a dictionary, so it also works for any character. Each program runs against the same five tests: a true anagram, a false one, two empty strings, different lengths, and listen versus silent.
What are the tips and tricks for an easy Valid Anagram solution?
Spot the pattern first. Phrases like “same letters,” “rearranged,” “permutation of” or “same frequency” all point to counting characters.
- Check the length first. Different lengths can never be anagrams, so return false before doing any real work.
- Use one counter, not two. Add for one string, subtract for the other, then check for zeros. It saves memory and a comparison loop.
- Pick an array for small alphabets. With only lowercase letters,
int[26]andc - 'a'is faster and simpler than a hash map. - Know the Python shortcut.
Counter(s) == Counter(t)is a clean one-liner, but be ready to explain what it does underneath. - Ask about Unicode. A great follow-up question is what happens with emojis or accented letters. A hash map keyed by character is the safer choice there.
What are the common mistakes with Valid Anagram?
- Skipping the length check, so
aandabslip through in some versions. - Using a 26-slot array for wider input. Capitals, spaces or Unicode break it. In Java,
'A' - 'a'is negative and throws anArrayIndexOutOfBoundsException. In Rust debug builds,a - b'a'panics on overflow. - Comparing only the set of letters, which ignores how many times each letter appears.
- Calling the sorting answer O(n) when the sort makes it O(n log n).
Where is the Valid Anagram pattern used in the real world?
Character and word counting sits behind a lot of everyday software. Spell checkers and word games group words by their letters. Plagiarism and search tools compare word frequencies between documents, and log analysis tools count how often each error appears.
The same frequency table idea also powers inventory checks, where you compare what was ordered with what was shipped.
Which earlier posts should you read before Valid Anagram?
If you are new to the series, start with Day 1, Two Sum, where the hash map idea first shows up. Then read Day 2, Best Time to Buy and Sell Stock to practise single-pass thinking, and Day 3, Contains Duplicate for the hash set.
Valid Anagram FAQs
What is the fastest way to check if two strings are anagrams?
Count each character with a fixed array or hash map in one pass, then check that every count is zero. That runs in O(n) time.
Is sorting a valid way to solve Valid Anagram?
Yes. Sorting both strings and comparing them is correct and easy to write, but it takes O(n log n) time instead of O(n).
Why is the counting solution O(1) space?
The count array always has 26 slots for lowercase letters, so its size does not grow with the input.
How do I handle Unicode or uppercase letters?
Use a hash map keyed by character instead of a 26-slot array. If the problem says case should not matter, convert both strings to lowercase first.
Is Valid Anagram asked in coding interviews?
Yes, it is a very common warm-up question. It often leads into Group Anagrams and Find All Anagrams in a String.
Conclusion
Valid Anagram comes down to one idea: count the letters once, and let the counts do the comparing. Start with the sorting version if you are stuck, then rewrite it with a 26-slot array and say the O(n) time and O(1) space out loud. Once that feels easy, try Group Anagrams without looking at the solution. In the next posts, we will keep building on hashing and counting.
