Given two strings, determine if they are anagrams or not.
For example, all these pairs are anagrams as lhs can be rearranged to rhs and vice-versa –
silent = listen
Tom Marvolo Riddle = I am Lord Voldemort
William Shakespeare = I am a weakish speller
incest = insect
A simple solution would be to sort given strings. If the strings become equal after sorting, they are anagrams. The time complexity of above solution is O(nlog(n)).
We can also solve this problem in O(n) time. The idea is to maintain frequency of each character of first string in a map or a count array. Then for each character of the second string, we decrement its frequency and return false if the frequency becomes negative or the character is not present in the map.
C++ implementation –
using namespace std;
// Function to check if X and Y are anagrams or not
bool isAnagram(string X, string Y)
// if X's length is not same as Y's, they can't be anagram
if (X.length() != Y.length())
// create an empty map
unordered_map<int, int> freq;
// maintain count of each character of X in the map
for (char x: X)
// do for each character of Y
for (char y: Y)
// if y is not found in map i.e. either y is not present
// in string X or has more occurences in string Y
if (freq.find(y) == freq.end())
// decrease the frequency of y in the map
// if its frequency become 0, erase it from map
// return true if map becomes empty
// main function
string X = "tommarvoloriddle"; // Tom Marvolo Riddle
string Y = "iamlordvoldemort"; // I am Lord Voldemort
if (isAnagram(X, Y))
cout << "Anagram";
cout << "Not a Anagram";
The time complexity of above solution is O(n) assuming constant time operation for std::unordered_map. The auxiliary space used by the program is O(n).
Thanks for reading.