Valid Anagram - LeetCode Java Solution
Tags: java, datastructures, algorithms, leetcode
Published: 2023-08-11 10:43:00

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

In this blog, let’s solve [Valid Anagram](https://leetcode.com/problems/valid-anagram/) which is one of the [Blind 75 List of LeetCode Problems](https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions).

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

```java
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

```java
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

```java
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](https://medium.com/techsoftware/understanding-hashing-in-java-exploring-hashmap-and-hashset-b2c7d28453c)

Recommended YouTubers for LeetCode Problems:

1. [NeetCode](https://www.youtube.com/@NeetCode)

2. [Take U Forward](https://www.youtube.com/@takeUforward/featured)

Free Resources for Learning Data Structures and Algorithms:

1. [NeetCode Roadmap](https://neetcode.io/roadmap?utm_source=aswin)

2. [Striver’s SDE Sheet](https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/)

Recommended Courses for Learning Data Structures and Algorithms:

1. [NeetCode Courses](https://neetcode.io/courses?utm_source=aswin)
2. ZTM: Mastering the Coding Interview (Big Tech): Available on [Udemy](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.3919716491451706865583445&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fmaster-the-coding-interview-big-tech-faang-interviews%2F) and [ZTM Academy](https://academy.zerotomastery.io/a/aff_rml6679s/external?affcode=441520_dcwk-s8s)
3. ZTM: Mastering the Coding Interview: Available on [Udemy](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.391976131953022569348758&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fmaster-the-coding-interview-data-structures-algorithms%2F) and [ZTM Academy](https://academy.zerotomastery.io/a/aff_nqb6sg6w/external?affcode=441520_dcwk-s8s)
4. [Data Structures & Algorithms, Level-up for Coding Interviews Course](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.391975289945963380819471&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fcpp-data-structures-algorithms-levelup-prateek-narang%2F)
5. [Striver’s A2Z (Free) Course](https://takeuforward.org/strivers-a2z-dsa-course/strivers-a2z-dsa-course-sheet-2/)

Top Coursera Courses for Learning Data Structures and Algorithms:

1. [Coding Interview Preparation (Meta)](https://imp.i384100.net/QyNgyo)
2. [Algorithms Course Part I (Princeton University)](https://imp.i384100.net/KjqAe9)
3. [Algorithms Course Part II (Princeton University)](https://imp.i384100.net/VmbWyE)
4. [Data Structures and Algorithms Specialization (UC San Diego)](https://imp.i384100.net/g1AVOA)
5. [Algorithms Specialization (Stanford)](https://imp.i384100.net/75G7ag)

(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](https://medium.com/techsoftware) 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 🙂.