This problem checks whether two strings are anagrams of each other. Two strings are anagrams if they contain the exact same characters with the same frequency but possibly in a different order.
Steps
- First, check if the lengths of both strings are equal. If not, return
false. - Create a hashmap (or character counter) to store the frequency of characters in the first string.
- Iterate over the second string and decrease the corresponding frequency in the map.
- If a character is not found or the count goes below zero, return
false. - If all characters match, return
trueat the end.
Dry Run
Input: s = "anagram", t = "nagaram"
- Build map from
s:{a:3, n:1, g:1, r:1, m:1} - Scan
t:- n → found → decrement
- a → found → decrement
- g → found → decrement
- a → found → decrement
- r → found → decrement
- a → found → decrement
- m → found → decrement
- All values are zero → return
true
Time & Space Complexity
- Time Complexity: O(n), where n is the length of the strings
- Space Complexity: O(1), since the character set is limited to 26 lowercase letters
var isAnagram = function(s, t) {
if (s.length !== t.length) return false;
let map = {};
for (let i = 0; i < s.length; i++) {
if (!map[s[i]]) {
map[s[i]] = 1;
} else {
++map[s[i]];
}
}
for (let i = 0; i < t.length; i++) {
if (!map[t[i]] || map[t[i]] < 0) {
return false;
} else {
--map[t[i]];
}
}
return true;
};
#include <iostream>
#include <unordered_map>
using namespace std;
bool isAnagram(string s, string t) {
if (s.length() != t.length()) return false;
unordered_map<char, int> map;
for (char c : s) {
map[c]++;
}
for (char c : t) {
if (map.find(c) == map.end() || map[c] == 0)
return false;
map[c]--;
}
return true;
}
#include <stdio.h>
#include <string.h>
int isAnagram(char* s, char* t) {
if (strlen(s) != strlen(t)) return 0;
int map[256] = {0};
for (int i = 0; s[i]; i++) {
map[(int)s[i]]++;
}
for (int i = 0; t[i]; i++) {
if (map[(int)t[i]] == 0) return 0;
map[(int)t[i]]--;
}
return 1;
}
import java.util.HashMap;
public class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
HashMap<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
for (char c : t.toCharArray()) {
if (!map.containsKey(c) || map.get(c) == 0) {
return false;
}
map.put(c, map.get(c) - 1);
}
return true;
}
}
def isAnagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
map = {}
for ch in s:
map[ch] = map.get(ch, 0) + 1
for ch in t:
if ch not in map or map[ch] == 0:
return False
map[ch] -= 1
return True
