Check If Two Strings Are Anagrams

57.6k
0

Given two strings s and t, the task is to check whether both strings are anagrams of each other.

Two strings are called anagrams when they contain the same characters with the same frequency, but the order of characters can be different.

Example 1

Input: s=listen ,t=silent

Output: true

Explanation: Both strings contain the same characters with the same frequencies, so they are anagrams.

Example 2

Input:s= hello ,t=world

Output: false

Explanation: The strings do not contain the same characters with the same frequencies, so they are not anagrams.

Brute: Sorting

A straightforward way to solve this problem is to arrange the characters of both strings in the same order by sorting them. If the two strings are anagrams, then after sorting, they should become exactly identical. Imagine two boxes containing letter cards. One box contains the letters of "listen" and the other contains the letters of "silent". Although the letters are arranged differently, sorting both sets alphabetically results in the same sequence: "eilnst". Since the sorted strings match, we can conclude that the original strings are anagrams. This approach works because sorting eliminates differences in character order and groups identical characters in the same positions, making comparison easy.


Algorithm

  1. First check if the lengths of both strings are different because strings with different lengths cannot have the same number of characters.

  2. If the lengths are different, return false because one string has extra characters, so they cannot be anagrams.

  3. Sort the first string because sorting arranges all its characters in a fixed order.

  4. Sort the second string because sorting arranges its characters in the same fixed order.

  5. Compare both sorted strings because anagrams become exactly the same after sorting.

  6. If both sorted strings are equal, return true because both strings have the same characters with the same frequency.

  7. Otherwise, return false because the characters or their frequencies are different.

Dry Run

Brute: Sorting

Brute: Sorting

Solution

// C++ program to check if two strings are anagrams using sorting
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks if two strings are anagrams.
// Sorting puts same characters in same order.
bool isAnagram(string s, string t) {
// Different lengths cannot form anagrams.
if (s.length() != t.length()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
// Equal sorted strings mean same characters.
return s == t;
}
};
int main() {
// Driver code
string s = "listen";
string t = "silent";
Solution obj;
cout << (obj.isAnagram(s, t) ? "true" : "false");
return 0;
}

Optimal: Frequency Counting

The sorting approach is easy to understand, but sorting the strings requires extra time. We can improve the solution by counting the frequency of each character, reducing the time complexity from O(N log N) to O(N). The key observation is that for two strings to be anagrams, the order of characters does not matter; only the number of times each character appears is important. Imagine two students holding letter cards. One student has the cards "a, a, b, b" while the other has "b, a, a, b". Although the arrangement is different, both students possess exactly two 'a's and two 'b's. Since the character counts match, the sets of cards are identical. Similarly, two strings are anagrams if every character appears the same number of times in both strings. To check this, we count the occurrences of each character in the first string and then decrease those counts using the characters of the second string. If all frequencies become zero by the end, the strings are anagrams; otherwise, they are not.

Algorithm

  1. First check if the lengths of both strings are different because anagrams must have the same number of characters.

  2. If the lengths are different, return false because one string has extra characters and both strings cannot be anagrams.

  3. Create a frequency array of size 26 because it stores the count of each lowercase English character.

  4. Treat index 0 as 'a', index 1 as 'b', and so on because this helps us store each character count at a fixed position.

  5. Traverse the first string and increase the frequency of each character because we need to know how many times each character appears in the first string.

  6. Traverse the second string and decrease the frequency of each character because we are matching and removing the characters found in the second string.

  7. Check the frequency array after both traversals because all counts should become 0 if both strings are anagrams.

  8. If any count is not 0, return false because it means some character count is different.

  9. If all counts are 0, return true because both strings have the same characters with the same frequency.

Dry Run

Optimal: Frequency Counting

Optimal: Frequency Counting

Solution

// C++ program to check if two strings are anagrams
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks if two strings are anagrams.
// Anagrams have same characters.
// Character frequency must also be same.
bool isAnagram(string s, string t) {
// Different lengths cannot form anagrams.
if (s.length() != t.length()) {
return false;
}
vector<int> freq(26, 0);
for (char ch : s) {
freq[ch - 'a']++;
}
for (char ch : t) {
freq[ch - 'a']--;
}
for (int count : freq) {
// Non-zero count means frequency is different.
if (count != 0) {
return false;
}
}
return true;
}
};
int main() {
// Driver code
string s = "listen";
string t = "silent";
Solution obj;
cout << (obj.isAnagram(s, t) ? "true" : "false");
return 0;
}

  • Time Complexity:
    The algorithm traverses the first string once to count the frequency of each character and then traverses the second string once to update those frequencies. After that, it checks the frequency array, which contains only 26 positions corresponding to the lowercase English letters. Since this array has a fixed size, checking it takes constant time. Therefore, the overall time complexity is O(N), where N is the length of the strings.

  • Space Complexity:
    The algorithm uses a frequency array of size 26 to store the count of each lowercase English letter. Since the size of this array remains constant regardless of the input size, the extra memory used does not grow with the length of the strings. Therefore, the space complexity is O(1).

FAQs

What is an anagram?

Two strings are anagrams if both contain the same characters with the same frequency, but the order can be different.

Does order matter in anagrams?

No. Character order does not matter. Character count matters.

Can two strings of different lengths be anagrams?

No. Different lengths mean at least one string has an extra or missing character, so the strings cannot be anagrams.

Is sorting a valid approach?

Yes. Sorting both strings and comparing them is valid, but it takes O(N log N) time.

Why is frequency counting better?

Frequency counting checks character counts directly in O(N) time and avoids the extra sorting cost.

What if the string contains uppercase letters?

If uppercase letters are allowed, convert both strings to the same case or use a hashmap, based on the problem statement.

What if the string contains spaces?

Spaces should be counted only when the problem treats spaces as valid characters. Otherwise, ignore spaces before checking anagrams.

String

Read Similar Blogs

TrieArraysData StructuresHashingStringSorting

Design Add and Search Words Data Structure

Design a data structure that supports adding words and searching words later. The search word may contain lowercase letters and the dot character . . The dot . can match any one lowercase English l...

50.7k
StringRecursionArrays

Introduction to String Advanced

1. Basic Pattern Matching Problem Suppose a word needs to be searched inside a larger sentence or string. The goal is to find all starting positions where the smaller pattern exactly matches a part...

66.9k
String

Introduction to Prefix-Suffix in String

Given a string s , find the length of the longest proper prefix that is also a suffix. A proper prefix means the whole string itself is not allowed. So if s = "aaaa" , the answer is 3 , because "aa...

81.6k
Comments0