Valid Anagram solution and explanation
Nokia
Infosys
Mastercard
9 more videos on this problem
Valid Anagram - Leetcode 242 - PythonNeetCode · 12:01 · 892K views
LeetCode 242. Valid Anagram Solution Explained - JavaNick White · 6:23 · 57K views
Valid Anagram | LeetCode problem 242 | Top 150 interview question seriesTechnosage · 8:33 · 57K views
Valid Anagram - Leetcode 242 - Hashmaps & Sets (Python)Greg Hogg · 3:44 · 23K views
LeetCode 242. Valid Anagram Solution Explained - JavaEngineering Digest · 10:53 · 15K views
LeetCode 242: Valid Anagram | Beginner's Coding InterviewAbstracted Away · 5:19 · 10K views
Valid Anagram | LeetCode 242 | Facebook Coding Interview TutorialTerrible Whiteboard · 8:30 · 6K views
Valid Anagram - LeetCode 242 - JavaScriptAlgoJS · 4:26 · 5K views
Leetcode | 242. Valid Anagram | Easy | Java SolutionDeveloper Docs · 7:27 · 4K views
LeetCode 242: Valid Anagram [Python]Frederik Müller · 3:58 · 2K views
The problem
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104sandtconsist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Approach overview
Problem Overview: Given two strings s and t, determine whether t is an anagram of s. Two strings are anagrams if they contain the same characters with the same frequency, just arranged in a different order.
Approach 1: Sorting (O(n log n) time, O(1) or O(n) space)
Sort both strings and compare the results. If two strings are anagrams, their sorted forms must be identical because sorting places identical characters in the same order. The process is simple: convert both strings to arrays, apply a sorting algorithm, and check if the sorted outputs match. Sorting dominates the runtime, giving O(n log n) time complexity. Space complexity depends on the language implementation—some sorting algorithms operate in-place while others allocate extra memory. This approach works well when code clarity matters more than optimal performance and is easy to implement in languages with built-in sort functions.
Approach 2: Frequency Counting (O(n) time, O(1) space)
Count how many times each character appears in both strings and verify that the counts match. Use a fixed-size frequency array or a hash table where the key represents a character and the value represents its frequency. Iterate through string s and increment counts, then iterate through t and decrement them. If any count becomes negative or a character is missing, the strings are not anagrams. Because each character is processed once, the runtime is O(n). Space complexity is O(1) when the character set is fixed (for example, 26 lowercase English letters). This approach leverages concepts from string manipulation and efficient counting techniques often used with hash tables.
The key insight is that anagrams differ only in order, not in character distribution. Frequency counting directly checks this invariant, avoiding the cost of sorting.
Recommended for interviews: The frequency counting approach. Interviewers expect candidates to recognize that sorting is unnecessary and that character counts fully determine whether two strings are anagrams. Showing the sorting approach first demonstrates baseline problem solving. Switching to the O(n) counting solution shows algorithmic optimization and familiarity with hash-based counting patterns.
Approach 1: Approach 1: Sorting
This approach involves sorting both strings and comparing them. If they are anagrams, both sorted strings will be identical since an anagram is defined as a rearrangement of letters. The time complexity mainly depends on the sorting step, which is O(n log n), where n is the length of the strings. Space complexity is O(1) if sorting is done in-place, otherwise O(n) with additional space for sorted copies.
def is_anagram(s: str, t: str) -> bool:
return sorted(s) == sorted(t)
s = "anagram"
t = "nagaram"
print(is_anagram(s, t))import java.util.Arrays;
public class AnagramCheck {
public static boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] sArray = s.toCharArray();
char[] tArray = t.toCharArray();
Arrays.sort(sArray);
Arrays.sort(tArray);
return Arrays.equals(sArray, tArray);
}
public static void main(String[] args) {
String s = "anagram";
String t = "nagaram";
System.out.println(isAnagram(s, t));
}
}#include <iostream>
#include <algorithm>
bool isAnagram(std::string s, std::string t) {
if (s.size() != t.size()) {
return false;
}
std::sort(s.begin(), s.end());
std::sort(t.begin(), t.end());
return s == t;
}
int main() {
std::string s = "anagram";
std::string t = "nagaram";
std::cout << (isAnagram(s, t) ? "true" : "false") << std::endl;
return 0;
}function isAnagram(s, t) {
if (s.length !== t.length) {
return false;
}
const sortedS = s.split('').sort().join('');
const sortedT = t.split('').sort().join('');
return sortedS === sortedT;
}
let s = 'anagram';
let t = 'nagaram';
console.log(isAnagram(s, t));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int compare(const void* a, const void* b) {
return *(char*)a - *(char*)b;
}
bool isAnagram(char * s, char * t) {
if (strlen(s) != strlen(t)) {
return false;
}
qsort(s, strlen(s), sizeof(char), compare);
qsort(t, strlen(t), sizeof(char), compare);
return strcmp(s, t) == 0;
}
int main() {
char s[] = "anagram";
char t[] = "nagaram";
printf("%s\n", isAnagram(s, t) ? "true" : "false");
return 0;
}using System;
public class AnagramCheck {
public static bool IsAnagram(string s, string t) {
if (s.Length != t.Length) {
return false;
}
char[] sArray = s.ToCharArray();
char[] tArray = t.ToCharArray();
Array.Sort(sArray);
Array.Sort(tArray);
return new string(sArray) == new string(tArray);
}
public static void Main() {
string s = "anagram";
string t = "nagaram";
Console.WriteLine(IsAnagram(s, t));
}
}The Python sorted() function is used to sort both strings. We then utilize equality checks to see if the sorted lists match, indicating that one string is an anagram of the other.
Time Complexity: O(n log n), Space Complexity: O(n) due to sorting operation.
Approach 2: Approach 2: Frequency Counting
This approach uses two arrays (or hashmaps for more general cases) to count the frequency of each character in both strings. Since the problem constraints specify lowercase English letters, array indices (0-25) can be used to count character occurrences.
def is_anagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
return all(x == 0 for x in count)
s = "anagram"
t = "nagaram"
print(is_anagram(s, t))public class AnagramCheck {
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 s = "anagram";
String t = "nagaram";
System.out.println(isAnagram(s, t));
}
}#include <iostream>
#include <vector>
bool isAnagram(std::string s, std::string t) {
if (s.size() != t.size()) {
return false;
}
std::vector<int> count(26, 0);
for (int 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;
}
int main() {
std::string s = "anagram";
std::string t = "nagaram";
std::cout << (isAnagram(s, t) ? "true" : "false") << std::endl;
return 0;
}function isAnagram(s, t) {
if (s.length !== t.length) {
return false;
}
const count = Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
count[t.charCodeAt(i) - 'a'.charCodeAt(0)]--;
}
return count.every(c => c === 0);
}
let s = 'anagram';
let t = 'nagaram';
console.log(isAnagram(s, t));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isAnagram(char * s, char * t) {
if (strlen(s) != strlen(t)) {
return false;
}
int count[26] = {0};
for (int i = 0; i < strlen(s); i++) {
count[s[i] - 'a']++;
count[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (count[i] != 0) {
return false;
}
}
return true;
}
int main() {
char s[] = "anagram";
char t[] = "nagaram";
printf("%s\n", isAnagram(s, t) ? "true" : "false");
return 0;
}using System;
public class AnagramCheck {
public static bool 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[i] - 'a']++;
count[t[i] - 'a']--;
}
foreach (int c in count) {
if (c != 0) {
return false;
}
}
return true;
}
public static void Main() {
string s = "anagram";
string t = "nagaram";
Console.WriteLine(IsAnagram(s, t));
}
}Using Python's list for counting the occurrence of each letter, this approach confirms anagrams by net-zero arrays post-evaluation, connoting equivalent character makeup.
Time Complexity: O(n), Space Complexity: O(1) limited to a fixed number of unique counts.
Approach 3: Counting
We first determine whether the length of the two strings is equal. If they are not equal, the characters in the two strings must be different, so return false.
Otherwise, we use a hash table or an array of length 26 to record the number of times each character appears in the string s, and then traverse the other string t. Each time we traverse a character, we subtract the number of times the corresponding character appears in the hash table by one. If the number of times after subtraction is less than 0, the number of times the character appears in the two strings is different, return false. If after traversing the two strings, all the character counts in the hash table are 0, it means that the characters in the two strings appear the same number of times, return true.
The time complexity is O(n), the space complexity is O(C), where n is the length of the string; and C is the size of the character set, which is C=26 in this problem.
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false;
}
const cnt = new Array(26).fill(0);
for (let i = 0; i < s.length; ++i) {
++cnt[s.charCodeAt(i) - 'a'.charCodeAt(0)];
--cnt[t.charCodeAt(i) - 'a'.charCodeAt(0)];
}
return cnt.every(x => x === 0);
}func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
cnt := [26]int{}
for i := 0; i < len(s); i++ {
cnt[s[i]-'a']++
cnt[t[i]-'a']--
}
for _, v := range cnt {
if v != 0 {
return false
}
}
return true
}impl Solution {
pub fn is_anagram(s: String, t: String) -> bool {
let n = s.len();
let m = t.len();
if n != m {
return false;
}
let mut s = s.chars().collect::<Vec<char>>();
let mut t = t.chars().collect::<Vec<char>>();
s.sort();
t.sort();
for i in 0..n {
if s[i] != t[i] {
return false;
}
}
true
}
}Approach 4: Default Approach
impl Solution {
pub fn is_anagram(s: String, t: String) -> bool {
let n = s.len();
let m = t.len();
if n != m {
return false;
}
let (s, t) = (s.as_bytes(), t.as_bytes());
let mut count = [0; 26];
for i in 0..n {
count[(s[i] - b'a') as usize] += 1;
count[(t[i] - b'a') as usize] -= 1;
}
count.iter().all(|&c| c == 0)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting | Time Complexity: O(n log n), Space Complexity: O(n) due to sorting operation. |
| Approach 2: Frequency Counting | Time Complexity: O(n), Space Complexity: O(1) limited to a fixed number of unique counts. |
| Counting | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting | O(n log n) | O(1) to O(n) | Quick implementation using built-in sort when performance is not critical |
| Frequency Counting (Hash Table / Array) | O(n) | O(1) | Optimal solution for interviews and large inputs |
Frequently asked questions
Is Valid Anagram easy or hard?
Valid Anagram is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge focuses on recognizing that character frequency comparison is more efficient than sorting.
Valid Anagram Python/Java solution
In Python, the common approach uses a dictionary or a 26-length list to track character frequencies. In Java, developers typically use an int array of size 26 or a HashMap<Character, Integer>. Both implementations achieve O(n) time complexity with constant extra space for lowercase letters.
How to solve Valid Anagram in O(n)?
Use a frequency array or hash map to count characters. First iterate through string s and increment the count for each character. Then iterate through t and decrement the corresponding counts. If any count becomes negative or the lengths differ, the strings are not anagrams. Processing each character once gives O(n) time complexity.
What is the best approach for Valid Anagram?
The frequency counting approach is the most efficient. Count the occurrence of each character in the first string and subtract counts while scanning the second string. If all counts return to zero, the strings are anagrams. This runs in O(n) time with O(1) space for a fixed alphabet.
Is Valid Anagram asked at Google/Amazon/Meta?
Valid Anagram appears frequently in technical interview practice sets and has been reported in screening rounds for companies such as Amazon, Meta, and Google. The problem tests understanding of hash tables, string processing, and time complexity optimization.
What data structure is used in Valid Anagram?
The optimal solution uses a hash table or a fixed-size frequency array. The structure stores how many times each character appears. Updating counts while scanning the strings allows constant-time lookups and efficient verification.
What is the time complexity of Valid Anagram?
The optimal solution runs in O(n) time because each character in the strings is processed once. The sorting approach takes O(n log n) due to the sorting step. Frequency counting with a hash table or fixed-size array achieves linear time.