Write a program to check two strings are anagrams

1. using arrays.sort

   sort both strings and compare the sorted strings

   Time Complexity: O(nLogn)

   Auxiliary space: O(1).

    import java.util.*;
   
    public class Main {
        public static void main(String[] args) {
            System.out.println(isAnagram("Race", "Care"));
        }
   
        public static boolean isAnagram(String str1, String str2) {
            // length check 
            if (str1.length() != str2.length()) return false;
   
            // convert strings to char array
            char[] charArray1 = str1.toLowerCase().toCharArray();
            char[] charArray2 = str2.toLowerCase().toCharArray();
   
            // sort the char array
            Arrays.sort(charArray1);
            Arrays.sort(charArray2);
   
            // if sorted char arrays are same
            // then the string is anagram
            return Arrays.equals(charArray1, charArray2);
        }
    }
   

2. using count array

   This method assumes that the set of possible characters in both strings is small. In the following implementation, it is assumed that the characters are stored using 8 bits and there can be 256 possible characters.

   • Create an array named count of 256 length

   • Iterate over the first string str1

   • In each iteration, we increment the count of the first String str1 and decrement the count of the second String str2

   • If the count of any character is not 0 at the end, it means two Strings are not anagrams

     Time Complexity: O(n)

     Auxiliary space: O(n)

public class Main {
    public static void main(String[] args) {
        System.out.println(isAnagram("Race", "Care"));
    }

    public static boolean isAnagram(String str1, String str2) {
        // length check 
        if (str1.length() != str2.length()) return false;

        int[] count = new int[256];
        for (int i = 0; i < str1.length(); i++) {
            count[str1.charAt(i)]++;
            count[str2.charAt(i)]--;
        }
        for (int i = 0; i < 256; i++) {
            if (count[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

1. using hashMap

   We can optimize the space complexity of the above method by using HashMap instead of initializing 256 characters array. So in this approach, we will first count the occurrences of each unique character with the help of HashMap for the first string. Then we will reduce the count of each character when we encounter them in the second string. Finally, if the count of each character in the hash map is 0 then it means both strings are anagrams else not

    public class Main {
        public static void main(String[] args) {
            System.out.println(isAnagram("Race", "Care"));
        }
   
        public static boolean isAnagram(String str1, String str2) {
            // Check if both string has same length or not
                 if (str1.length() != str2.length()) {
                return false;
            }
   
            str1 = str1.toLowerCase();
            str2 = str2.toLowerCase();
   
            Map<Character, Integer> map = new HashMap<>();
   
            for (int i = 0; i < str1.length(); i++) {
                char ch = str1.charAt(i);
                if (map.containsKey(ch)) {
                    map.put(ch, map.get(ch) + 1);
                } else {
                    map.put(ch, 1);
                }
            }
   
            for (int i = 0; i < str2.length(); i++) {
                char ch = str2.charAt(i);
                if (!map.containsKey(ch)) {
                    return false;
                } else if (map.get(ch) == 1) {
                    map.remove(ch);
                } else {
                    map.put(ch, map.get(ch) - 1);
                }
            }
   
            // Return true if the HashMap is empty
            return map.isEmpty();
    }