Valid Anagram - LeetCode Java Solution

Hello readers, let’s solve a LeetCode problem today.

In this blog, let’s solve Valid Anagram which is one of the Blind 75 List of LeetCode Problems.

This is a very good LeetCode Easy problem for beginners.

There are multiple potential solutions for this problem, which we will go through in this blog.

Understand the problem

• 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.
• Given two strings s and t:
  • return true , if t is an anagram of s
  • return false otherwise.

Understand the test cases

Example 1:

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

• The input strings “anagram" and "nagaram" exactly contain 3 - ’a’, 1 - ‘g’, 1 - ‘m’, 1 - ‘n’ and 1 - ‘r’.
• So, "nagaram" can be formed by rearranging the letters of “anagram". And hence, they are both anagrams of each other.

Example 2:

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

• The string “car” does not contain the character ‘t’ from the string s: “rat”, so these are not anagrams.

Brute force Approach: Sorting

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        Arrays.sort(sc);
        Arrays.sort(tc);
        if(new String(sc).equals(new String(tc)))
            return true;
        return false;
    }
}

Key Points:

• The above code checks if two strings, s and t, are anagrams by converting them into character arrays, sorting the arrays in ascending order, and then comparing the sorted arrays for equality.
• If the sorted arrays of characters are equal, it means that the strings have the same characters in the same frequencies, indicating that they are anagrams of each other.
• The code returns true if the strings are anagrams, and false otherwise.

Time complexity: O(N log N)

• The time complexity of the above code is O(N log N), where N is the length of the longer string between s and t. This is because the code uses Arrays.sort() to sort the character arrays sc and tc.
• The time complexity of the Arrays.sort() method is O(n log n) in the average case. Therefore, the overall time complexity is dominated by the sorting operation.

Space complexity: O(N)

• The space complexity of the code is O(N), where N is the length of the longer string between s and t.
• This is because the code creates two character arrays, sc and tc, which store the characters of the input strings.
• The length of each character array is equal to the length of the respective input string. Therefore, the space required by the character arrays is proportional to the length of the longer string.

Better Approach: Count using two HashMaps

class Solution {
    public boolean isAnagram(String s, String t) {
        HashMap<Character, Integer> count1 = new HashMap<>();
        HashMap<Character, Integer> count2 = new HashMap<>();
        count1 = count(count1, s);
        count2 = count(count2, t);
        return count1.equals(count2) ? true : false;
    }
    public HashMap<Character, Integer> count(HashMap<Character, Integer> count, String str) {
        for(int i=0; i<str.length(); i++) {
            Character c=str.charAt(i);
            if(count.containsKey(c)) {
                count.put(c, count.get(c)+1);
                continue;
            }
            count.put(c, 1);
        }
        return count;
    }
}

Key Points:

• HashMaps count1 and count2 are used to count the number of characters in the given two strings s and t respectively.
• The function count() is used to traverse the given string, calculate the number of occurrences of a character and store them in the count HashMap and return it.
• Finally, count1 and count2 are compared for equality to verify of the given two strings are anagrams of each other or not.

Time Complexity: O(N)

• The time complexity of the given code is O(N), where N is the total number of characters in both strings combined. This is because the code iterates over each character in the strings once while building the frequency count in the count() method.
• Since the count() method is called twice, once for each input string, the total time complexity is O(x + y), where x and y are the lengths of the input strings s and t respectively.
• However, since we typically ignore constant factors and focus on the dominant term, the time complexity is simplified to O(N).

Space Complexity: O(1) or Constant

• The space complexity of the code is O(k), where k is the number of unique characters across both strings.
• In the worst-case scenario, each unique character in the strings will be stored as a key in the count1 and count2 HashMaps. Therefore, the space required by HashMaps is proportional to the number of unique characters.
• Since the total number of unique characters is typically much smaller than the length of the strings, we can consider the space complexity to be O(1) or constant.

Optimal Approach: Count using a frequency array

public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] alphabet = new int[26];
        for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
        for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
        for (int i : alphabet) if (i != 0) return false;
        return true;
    }
}

Key Points:

• In the above code, a size 26 int array: alphabet is created as a frequency array for each letter in the Alphabet. The indices of the alphabet represent the 26 letters of the Alphabet. So, 0 represents ‘a’, 1 represents ‘b’ so on until 25 represents ‘z’.
• Then, we calculate the frequency of the characters:
  • We increment the alphabet array values for each of the characters of String s in the first iteration.
  • And then decrement the values of the same alphabet array with string t in the second iteration.
  • In both iterations, we perform the operations s.charAt(i) - 'a' and t.charAt(i) - 'a' . Here, the characters of the string s and string t are subtracted with the character ‘a’ to get an integer value of the letters that correspond to the alphabet array.
• If they are anagrams, the alphabet bucket should remain with the initial value of the array which is zero.
• So, the final iteration just checks if all values are zero, if any value is not zero, we return false and return true

Time complexity: O(N)

• The time complexity of the above code is O(n), where n is the length of the longer string between s and t. This is because the code iterates over each character in both strings only once, using two separate loops.
• The first loop counts the occurrences of characters in string s, and the second loop subtracts the occurrences of characters in string t. Finally, there is a third loop that checks if any count in the alphabet array is nonzero, indicating a mismatch in character counts between the two strings.

Space complexity: O(1) or Constant

• The space complexity of the code is O(1) or constant because uses an integer array, alphabet, of size 26 to store the counts of characters in the English alphabet.
• Regardless of the length of the input strings, the alphabet array remains a fixed size because it represents a fixed set of characters (lowercase English letters).
• Therefore, the space required by the array is constant and does not depend on the input size.

NeetCode Solution Video

https://youtu.be/9UtInBqnCgA

Recommended Resources to Learn Data Structures and Algorithms

Basics of DS Algo Blogs:

1. Hashing in Java

Recommended YouTubers for LeetCode Problems:

1. NeetCode

2. Take U Forward

Free Resources for Learning Data Structures and Algorithms:

1. NeetCode Roadmap

2. Striver’s SDE Sheet

Recommended Courses for Learning Data Structures and Algorithms:

1. NeetCode Courses
2. ZTM: Mastering the Coding Interview (Big Tech): Available on Udemy and ZTM Academy
3. ZTM: Mastering the Coding Interview: Available on Udemy and ZTM Academy
4. Data Structures & Algorithms, Level-up for Coding Interviews Course
5. Striver’s A2Z (Free) Course

Top Coursera Courses for Learning Data Structures and Algorithms:

1. Coding Interview Preparation (Meta)
2. Algorithms Course Part I (Princeton University)
3. Algorithms Course Part II (Princeton University)
4. Data Structures and Algorithms Specialization (UC San Diego)
5. Algorithms Specialization (Stanford)

(Note: The Coursera courses can be audited to get free access to the lectures)

🎙 Disclosure: Please note that some of the links mentioned on this page may be affiliate links. This means that if you click on one of these links and make a purchase, I may earn a small commission from the sale.

Who Am I?

I’m Aswin Barath, a Software Engineering Nerd who loves building Web Applications, now sharing my knowledge through Blogging during the busy time of my freelancing work life. Here’s the link to all of my craziness categorized by platforms under one place: https://linktr.ee/AswinBarath

Keep Learning

Now, I guess this is where I say goodbye 👋. But, hey it’s time for you to start learning with your newfound Knowledge(Power)👨‍💻👩‍💻. Good Job that you made it this far 👏 & Thank you so much for reading my Blog 🙂.