Home » Technical Interview Questions » String Interview Questions » Check whether two strings are anagram of each other

# Check whether two strings are anagram of each other

## Given two strings s1 and s2, write a function that says whether the two strings are anagram or not s2 is said to be a anagram if it contains same characters that of s1, but order can be different

### Example 1

INPUT
s1 = “abcd”
s2 = “cdbe”

OUTPUT
Given two strings are not anagram to each other as the string s1 does not contain all characters of s2

### Example 2

s1 = “tutorial cup”
s2 = “cup tutorial”

OUTPUT
Given two strings are anagram to each other

### Method 1(using sorting)

Time Complexity : O(nlogn)

## Algorithm

1. Sort the both strings

2. Compare the sorted strings

## C++ Program

```#include <bits/stdc++.h>
using namespace std;

//Prototype
void quickSort(char *arr, int start, int end);
int partition(char A[], int start, int end);

// It will swap two pointers
void swap(char *a, char *b)
{
char temp;
temp = *a;
*a   = *b;
*b   = temp;
}
//It will sort the given string
void quickSort(char S[], int start, int end)
{
int pi;    // Partitioning index //
if(start < end)
{
pi = partition(S, start, end);
quickSort(S, start, pi - 1);
quickSort(S, pi + 1, end);
}
}
int partition(char S[], int start, int end)
{
char pivot = S[end];
int i = (start - 1);
int j;

for (j = start; j <= end - 1; j++)
{
if(S[j] <= pivot)
{
i++;
swap(&S[i], &S[j]);
}
}
swap(&S[i + 1], &S[end]);
return (i + 1);
}

// function to check whether two strings are anagram of
// each other or not
bool anagrams(char *s1, char *s2)
{
// Get lenghts of both strings
int m = strlen(s1);
int n = strlen(s2);

// If length of both strings is not same, then they
// cannot be anagram to each other
if (m != n)
return false;

// Sort both strings
quickSort(s1, 0, m - 1);
quickSort(s2, 0, n - 1);

// Compare sorted strings
for (int i = 0; i < m;  i++)
if (s1[i] != s2[i])
return false;

return true;
}

int main()
{
char s1[] = "tutorial cup";
char s2[] = "cup tutorial";
if (anagrams(s1, s2))
{
cout<<"Given two strings are anagram to each other"<<endl;
}
else
{
cout<<"Given two strings are not anagram to each other"<<endl;
}

return 0;
}```

### Method 2

In this method the main idea is to count the occurences of the characters in both strings and compare them

## Algorithm

1. Build two count arrays for s1 and s2.
ie, for example 1
s1_count[‘a’] = 1, s1_count[‘b’] = 1, s1_count[‘c’] = 1, s1_count[‘d’] = 1.
s1_count[‘c’] = 1, s1_count[‘d’] = 1, s1_count[‘b’] = 1, s2_count[‘e’] = 1.

2. Compare two count arrays.
ie, for example 1
s1_count[‘a’] = 1 does not match with s2__count[‘a’](which is 0), so they are not anagram of each other

## C++ Program

```# include <bits/stdc++.h>
# define NO_OF_CHARS 256

using namespace std;

//If the given strings are anagrams, returns true else false
bool anagrams(char *s1, char *s2)
{
// Build count arrays for s1 and s2
int s1_count[NO_OF_CHARS] = {0};
int s2_count[NO_OF_CHARS] = {0};
int i;

// For each character in input strings, increment count in
// the corresponding count array
for (i = 0; s1[i] && s2[i];  i++)
{
s1_count[s1[i]]++;
s2_count[s2[i]]++;
}

// If any of the two operands is non-zero, then condition becomes true.
//If any string has more characters ie, s1 is "bfdd" and s2 is "bfd".
//If the below condition is not present, the function says above s1 and s2 are anagrams
//but, it is not true
if (s1[i] || s2[i])
return false;

// Compare count arrays
for (i = 0; i < NO_OF_CHARS; i++)
if (s1_count[i] != s2_count[i])
return false;

return true;
}

int main()
{
char s1[] = "abcde";
char s2[] = "acdef";
if (anagrams(s1, s2))
{
cout<<"Given two strings are anagram of each other"<<endl;
}
else
{
cout<<"The two strings are not anagram of each other"<<endl;
}

return 0;
}```

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions