Valid Anagram

Thought Process

To determine if two strings are valid anagrams, we can use either a frequency counting approach or a sorting approach. Here are two approaches:

Approach 1: Frequency Counting - Use a frequency array to count the occurrences of each character in the first string. Decrement the count for each character in the second string. If all counts in the frequency array are zero, the strings are anagrams.

Approach 2: Sorting - Sort both strings and compare them. If they are identical, the strings are anagrams.

Approach 1: Hash Table

class Solution {
    public boolean isAnagram(String s, String t) {
        
        int[] sHash = new int[26];
        for(int i=0;i<s.length();i++){
            
            char ch = s.charAt(i);
            sHash[ch-'a']++;
        }
        for(int i=0;i<t.length();i++){

            char ch = t.charAt(i);
            sHash[ch-'a']--;
        }
        for(int i=0;i<25;i++){

            if(sHash[i]!=0)
                return false;
        }
        return true;
    }
}

Approach 2: Sorting

class Solution {
    public boolean isAnagram(String s, String t) {

        char[] charArray1 = s.toCharArray();
        char[] charArray2 = t.toCharArray();

        Arrays.sort(charArray1);
        Arrays.sort(charArray2);

        if(Arrays.equals(charArray1,charArray2))
            return true;
        else
            return false;
        }
}

Code Complexity

Time Complexity: O(n) or O(n log n)

The frequency counting approach is linear in time, while the sorting approach has a time complexity of O(n log n) due to sorting.

Space Complexity: O(1)

Both approaches use constant extra space, making them highly efficient.