SimuVedaAlgorithms Lab Open in the lab

Hashing / Intermediate

Valid Anagram Visualizer

Count every letter of the first word up, and every letter of the second word down. They are anagrams only if every count ends at 0.

Start the Valid Anagram simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Is "silent" an anagram of "listen"?
  2. "l" from the first word: count up to 1.
  3. "i" from the first word: count up to 1.
  4. "s" from the first word: count up to 1.
  5. "t" from the first word: count up to 1.
  6. "e" from the first word: count up to 1.
  7. "n" from the first word: count up to 1.
  8. "s" from the second word: count down to 0.
  9. "i" from the second word: count down to 0.
  10. "l" from the second word: count down to 0.
  11. "e" from the second word: count down to 0.
  12. "n" from the second word: count down to 0.
  13. "t" from the second word: count down to 0.
  14. Every count is back to 0. "listen" and "silent" are anagrams.

Try it with your own input →

Valid anagram in Java, Python, C++, C and JavaScript

boolean isAnagram(String s, String t) {
  if (s.length() != t.length()) return false;
  int[] count = new int[26];
  for (char c : s.toCharArray()) count[c - 'a']++;
  for (char c : t.toCharArray()) count[c - 'a']--;
  for (int x : count) if (x != 0) return false;
  return true;
}
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for c in s:
        count[ord(c) - ord('a')] += 1
    for c in t:
        count[ord(c) - ord('a')] -= 1
    return all(x == 0 for x in count)
bool isAnagram(const string& s, const string& t) {
  if (s.size() != t.size()) return false;
  int count[26] = {0};
  for (char c : s) count[c - 'a']++;
  for (char c : t) count[c - 'a']--;
  for (int x : count) if (x != 0) return false;
  return true;
}
#include <string.h>

int isAnagram(const char* s, const char* t) {
  if (strlen(s) != strlen(t)) return 0;
  int count[26] = {0};
  for (; *s; s++) count[*s - 'a']++;
  for (; *t; t++) count[*t - 'a']--;
  for (int i = 0; i < 26; i++) if (count[i] != 0) return 0;
  return 1;
}
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Array(26).fill(0);
  for (const c of s) count[c.charCodeAt(0) - 97]++;
  for (const c of t) count[c.charCodeAt(0) - 97]--;
  for (const x of count) if (x !== 0) return false;
  return true;
}

In an interview

LeetCode 242, Valid Anagram: do two words use exactly the same letters the same number of times?

An int[26] array is enough for lowercase letters and counts as O(1) space. Sorting both words also works but is O(n log n). Different lengths can be rejected at once.

More hashing