Valid Anagram
Valid Anagram is a easy arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (26 letter counters), runs in O(n) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (cross off matching letters) up.
Problem
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
A string is an anagram of another when it uses exactly the same letters the same number of times, possibly in a different order. For instance "night" and "thing" are anagrams, but "aab" and "abb" are not.
Examples
Example 1
- Input
s = "listen", t = "silent"- Output
true- Why
- Both words use one each of e, i, l, n, s, t.
Example 2
- Input
s = "apple", t = "paple"- Output
true- Why
- Same letters with the same counts (two p's), just in another order.
Example 3
- Input
s = "seed", t = "deed"- Output
false- Why
- "seed" has an s and only one d, while "deed" has two d's and no s.
Constraints
1 <= s.length, t.length <= 5 * 10^4sandtcontain only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (cross off matching letters) | O(n²) | O(n) |
| Better (sort and compare) | O(n log n) | O(n) |
| Optimal (26 letter counters) | O(n) | O(1) |
1Brute force (cross off matching letters)
O(n²)Each of the n letters may scan all of t.O(n)The `used` array.For every letter of s, look for an unused copy of it in t and mark it as used. If some letter has no partner, or the lengths differ, the strings are not anagrams.
- If the lengths differ, return false.
- Keep a boolean array
usedfor positions of t. - For each character c of s, scan t for an unused position j with t[j] == c; if none, return false; else mark it used.
- Return true.
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int n = t.length();
boolean[] used = new boolean[n];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
boolean found = false;
for (int j = 0; j < n; j++) {
if (!used[j] && t.charAt(j) == c) {
used[j] = true;
found = true;
break;
}
}
if (!found) return false;
}
return true;
}
}class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
n = len(t)
used = [False] * n
for c in s:
found = False
for j in range(n):
if not used[j] and t[j] == c:
used[j] = True
found = True
break
if not found:
return False
return Trueclass Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int n = t.size();
vector<bool> used(n, false);
for (char c : s) {
bool found = false;
for (int j = 0; j < n; j++) {
if (!used[j] && t[j] == c) {
used[j] = true;
found = true;
break;
}
}
if (!found) return false;
}
return true;
}
};function isAnagram(s, t) {
if (s.length !== t.length) return false;
const n = t.length;
const used = new Array(n).fill(false);
for (const c of s) {
let found = false;
for (let j = 0; j < n; j++) {
if (!used[j] && t[j] === c) {
used[j] = true;
found = true;
break;
}
}
if (!found) return false;
}
return true;
}2Better (sort and compare)
O(n log n)Dominated by the two sorts.O(n)Character arrays copied from the strings.Anagrams become the same string once their letters are sorted. Sort the characters of both strings and compare the results.
- If the lengths differ, return false.
- Sort the characters of s and of t.
- Return whether the sorted arrays are equal.
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
char[] a = s.toCharArray(), b = t.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
return Arrays.equals(a, b);
}
}class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return len(s) == len(t) and sorted(s) == sorted(t)class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};function isAnagram(s, t) {
if (s.length !== t.length) return false;
return [...s].sort().join("") === [...t].sort().join("");
}3Optimal (26 letter counters)
O(n)One pass over both strings plus 26 checks.O(1)A fixed array of 26 integers.Use one array of 26 counters. Add one for each letter of s and subtract one for each letter of t. The strings are anagrams exactly when every counter ends at zero.
- If the lengths differ, return false.
- For each index i: count[s[i] - 'a']++ and count[t[i] - 'a']--.
- Return true if all 26 counters are 0.
class Solution {
public 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;
}
}class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for a, b in zip(s, t):
count[ord(a) - 97] += 1
count[ord(b) - 97] -= 1
return all(c == 0 for c in count)class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int count[26] = {0};
for (size_t i = 0; i < s.size(); i++) {
count[s[i] - 'a']++;
count[t[i] - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
};function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++;
count[t.charCodeAt(i) - 97]--;
}
return count.every((c) => c === 0);
}Edge cases to test
- Different lengths: never anagrams
- Same letters but different counts, like "aab" and "abb"
- Identical strings are anagrams of each other
- Single-character strings
Hints
Hint 1
Two strings are anagrams exactly when every letter occurs the same number of times in both.
Hint 2
Sorting both strings and comparing works. Can you avoid the sort using the fact that there are only 26 letters?
FAQ
What is the best time complexity for Valid Anagram?
Optimal (26 letter counters) runs in O(n) time and O(1) extra space. One pass over both strings plus 26 checks.
Which pattern does Valid Anagram use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.
Is there a brute force solution for Valid Anagram?
Yes. Brute force (cross off matching letters) takes O(n²) time and O(n) space. For every letter of s, look for an unused copy of it in t and mark it as used.
Which edge cases should I test for Valid Anagram?
Different lengths: never anagrams; Same letters but different counts, like "aab" and "abb"; Identical strings are anagrams of each other; Single-character strings.