Practice › Strings
Valid Anagram
Easy · Strings · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Two strings are anagrams if one can be rearranged into the other. Print YES or NO.
Input
Two lines: strings s and t (lowercase letters).
Output
YES or NO.
Constraints
- 1 ≤ |s|, |t| ≤ 10^5
Count letters with an array of size 26.
Example 1
Input
anagram nagaram
Output
YES
Example 2
Input
rat car
Output
NO
Hints
- Anagrams contain exactly the same letters the same number of times.
- Count letters with an int array of size 26: +1 for each letter of s, −1 for each letter of t.
Approach
If the lengths differ, the answer is NO. Otherwise count: add 1 for each letter of s and subtract 1 for each letter of t in a 26-slot array. The strings are anagrams if every slot ends at 0. Sorting both strings and comparing also works, in O(n log n).
Complexity: O(n) time · O(1) extra space (26 counters)
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
int cnt[26] = {0};
for (char c : s) cnt[c - 'a']++;
for (char c : t) cnt[c - 'a']--;
bool ok = s.size() == t.size();
for (int i = 0; i < 26; i++)
if (cnt[i] != 0) ok = false;
cout << (ok ? "YES" : "NO") << "\n";
return 0;
}Python solution
from collections import Counter
s = input().strip()
t = input().strip()
print("YES" if Counter(s) == Counter(t) else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next(), t = sc.next();
int[] cnt = new int[26];
for (char c : s.toCharArray()) cnt[c - 'a']++;
for (char c : t.toCharArray()) cnt[c - 'a']--;
boolean ok = s.length() == t.length();
for (int x : cnt)
if (x != 0) ok = false;
System.out.println(ok ? "YES" : "NO");
}
}