Valid Anagrams

In the problem “Valid Anagrams” we have given two strings str1 and str2. Find out that both the strings are anagrams or not. If they are anagrams return true else return false.

Example

Input:

str1 = “abcbac”

str2 = “aabbcc”

Output:

true

Explanation:

Since str2 can be formed by rearranging all the words of str1 so the output will be “true”.

Algorithm

1. Find the length of both the string
2. sort both the string alphabetically
3. Compare both the string
4. If equal return “true” else return “false”

Explanation

Anagrams are the same words that can be arranged in an order in which both the strings look similar and makes a single and identical word after rearranging them.

Ex: silent is the word that can be arranged in an order and make a word listen, so both the words are anagrams of each other.

Our code is to find whether the given strings are valid anagrams or not, so our main idea is to find first the length of the string, if the length of both the string is found to be similar then only we move further, otherwise not, because strings can’t be the anagrams if their lengths are not similar. So from there, we return false.

Our next logic is to arrange them in ascending order so that each character comes in order, so we defined a function “sort”. Both of the strings which are passed into the sort function converted into a temporary array which is going to sort the array and return the string into str1, so sorted string stored string store in the same string, this will happen with both of the strings, and we get the sorted strings.

silent= [s,i,l,e,n,t] //character array
listen= [l,i,s,t,e,n] //character array

sorted array=[e,i,l,n,s,t] // sorted array of silent stored in the str1
sorted array=[e,i,l,n,s,t] // sorted array of listen stored in the str2

Then with the for loop we will compare every single index of both the strings if the same characters are found to be identical, then they are anagrams and return true and “true” prints and false prints if it is returned false.

Implementation

C++ program for Valid Anagrams

#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

bool areAnagram(string str1, string str2)
{
    //getting length of both the strings
    int n1 = str1.length();
    int n2 = str2.length();

    //Checking if both the strings are of same length
    if (n1 != n2)
        return false;

    //Sorting both the string alphabetically
    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());

    //checking each character of string is equal to
    //another character of string
    if (str1 != str2)
        return false;

    return true;
}

int main ()
{
    string str1 = "silent";
    string str2 = "listen";
    if(areAnagram(str1,str2))
        cout << "true";
    else
        cout << "false";
    return 0;
}

true

Java program for Valid Anagrams

import java.util.Arrays;
import java.util.Scanner;
class validAnagrams
{
  public static String sort(String str)
  {
      char temp[] = str.toCharArray();
      Arrays.sort(temp);
      return new String(temp);
  }
  public static boolean areAnagram(String str1, String str2)
  {
    //getting length of both the strings
    int length1 = str1.length();
    int length2 = str2.length();

    //Checking if both the strings are of same length
    if (length1 != length2)
    {
      return false;
    }

    //Sorting both the string alphabetically
    str1=sort(str1);
    str2=sort(str2);

    //checking each character of string is equal to
    //another character of string
    for (int i = 0; i < length1; i++)
    {
        if (str1.charAt(i) != str2.charAt(i))
        {
            return false;
      }
    }

        return true;
    }
  public static void main(String [] args)
  {
    String str1 = "silent";
    String str2 = "listen";
    System.out.println(areAnagram(str1,str2)?"true":"false");

  }
}

true

Complexity Analysis for Valid Anagrams

Time Complexity

O(nlogn) where n is the size of the string. Here we sort the string on the basis of character which takes nlogn time.

Space Complexity

O(1) because we don’t use any extra space at here.