---

Problem: Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Constraints:

• 1 <= s.length, t.length <= 5 * 10<sup>4</sup>

• s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

---

Solution 1

Given the constraints provided, we can adapt the solution using a character count array to keep track of the frequencies of characters in both strings.

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

        if (s.length() != t.length()) {
            return false;
        }

        int[] count = new int[26];

        for (char ch : s.toCharArray()) {
            count[ch - 'a']++;
        }

        for (char ch : t.toCharArray()) {
            if (count[ch - 'a'] == 0) {
                return false;
            }
            count[ch - 'a']--;
        }

        return true;
    }
}

1. Length Check:

   • The initial if condition checks if the lengths of strings s and t are different. If their lengths differ, then the strings cannot be anagrams, and the method immediately returns false.

2. Character Count Array:

   • An integer array count of size 26 (representing the 26 lowercase letters of the English alphabet) is initialized. This array will be used to keep track of the frequency of each letter in the strings.

   • The index of the array represents a character's position in the alphabet. For example, count[0] represents the frequency of 'a', count[1] represents the frequency of 'b', and so on.

3. Counting Frequencies in String s:

   • The first for-each loop iterates through each character ch in the string s.

   • For each character, its frequency in the count array is incremented. This is achieved by converting the character to an index between 0 and 25 (inclusive) using the expression ch - 'a'.

4. Checking Frequencies in String t:

   • The second for-each loop iterates through each character ch in the string t.

   • For each character, its frequency in the count array is decremented. Before decrementing, the current frequency is checked. If the frequency is already 0 (meaning the character is not present in string s), then the method returns false, indicating that the strings are not anagrams.

5. Final Check:

   • After processing all characters in both strings, if the method has not returned false, it indicates that all characters in string t have frequencies that are either equal to or less than their corresponding frequencies in string s. In this case, the method returns true, indicating that the strings are anagrams.

Complexities

Time Complexity: O(n)

The time complexity of an algorithm represents the amount of time taken by an algorithm to run as a function of the length of the input.

1. Iterating Over Strings:

   • Both for-each loops in the code iterate over each character in the strings s and t respectively.

   • In the worst-case scenario, if both strings are of length n, the loops will iterate n times each. Thus, the time complexity for iterating over both strings is O(n).

2. Character Counting:

   • Within each iteration of the loops, the code performs constant-time operations such as array access (count[ch - 'a']++ and count[ch - 'a']--), arithmetic operations, and comparisons.

   • The constant-time operations inside the loops do not affect the overall time complexity, so they can be ignored for the purpose of analyzing the overall complexity.

Combining the above points, the overall time complexity of the isAnagram method is O(n).

Space Complexity: O(1)

The space complexity of an algorithm represents the amount of memory space required by an algorithm to run as a function of the length of the input.

1. Character Count Array:

   • The integer array count of size 26 is initialized to keep track of the frequency of each letter. Since the size of the array (26) is constant and does not depend on the length of the input strings, its space complexity is considered constant, i.e., O(1).

2. Other Variables:

   • Apart from the character count array, the method uses a few other variables such as the input strings s and t, and a character ch for iteration. These variables have a constant amount of space allocated, and their combined space complexity is also considered constant, i.e., O(1).

Thus, the space complexity of the isAnagram method is O(1) or constant space, as the space used is not dependent on the size of the input strings.

---

Solution 2

If the inputs can contain Unicode characters, the character count array method becomes impractical due to the large Unicode character set. Instead, we can use a HashMap to store the frequency of each character in both strings and then compare the maps.

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

        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Integer> map = new HashMap<>();

        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) - 1);
            if (map.get(c) < 0 ) {
                return false;
            }
        }

        return true;
    }
}

1. Length Check:

   • The initial if condition checks if the lengths of strings s and t are different. If their lengths differ, then the strings cannot be anagrams, and the method immediately returns false.

2. Character Frequency Map:

   • A HashMap named map is initialized to store the frequency of characters in string s. The keys of the map represent unique characters, and the values represent their frequencies.

3. Counting Frequencies in String s:

   • The first for-each loop iterates through each character c in the string s.

   • For each character, its frequency in the map is incremented using the put method along with getOrDefault to handle cases where the character is not already present in the map.

4. Checking Frequencies in String t:

   • The second for-each loop iterates through each character c in the string t.

   • It decreases the frequency count of each character in the map by 1 (or sets it to -1 if the character is not present).

   • If the frequency count of any character in the map becomes negative after decrementing, it means that the character appeared more times in t than in s, so the method returns false.

5. Final Check:

   • After processing all characters in both strings, if the method has not returned false by this point, it means that both strings have the same characters with the same frequencies (even if in different order). Therefore, the method returns true, indicating that s and t are anagrams of each other.

Complexities

Time Complexity: O(n)

1. Iterating Over Strings:

   • Both for-each loops in the code iterate over each character in the strings s and t respectively.

   • In the worst-case scenario, if both strings are of length n, the loops will iterate n times each. Thus, the time complexity for iterating over both strings is O(n).

2. Character Counting:

   • Within each iteration of the loops, the code performs constant-time operations such as map access (map.getOrDefault(c, 0)) and arithmetic operations.

   • The constant-time operations inside the loops do not affect the overall time complexity, so they can be ignored for the purpose of analyzing the overall complexity.

Combining the above points, the overall time complexity of the isAnagram method is O(n).

Space Complexity: O(1)

1. Character Frequency Map:

   • The HashMap map is initialized to store the frequency of characters in string s. The space occupied by the HashMap depends on the number of unique characters in s.

   • In the worst-case scenario, where all characters in the input strings are unique, the space complexity can be approximated to O(n), where n is the length of the input strings. This is because the size of the map could potentially grow linearly with the length of the input strings in the worst case.

2. Other Variables:

   • Apart from the HashMap, the method uses a few other variables such as the input strings s and t, and a character c for iteration. These variables have a constant amount of space allocated, and their combined space complexity is also considered constant, i.e., O(1).

Thus, the space complexity of the isAnagram method is O(n) in the worst-case scenario where all characters in the input strings are unique.