Strings - 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.

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: "nagaram" is an anagram of "anagram" word, we can form the word "nagaram" by re-arranging leters from "anagram" only once.

Input: s = "rat", t = "car"
Output: true
Explanation: "car" cannot be formed by re-arranging leters from "rat".

Constraints:

1 <= s.length, t.length <= 5 * 10⁴
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 - Using an array to store count of each character appearance
Solution 2 - Using two HashMaps to store count of each character appearance
Solution 3 - Using one HashMap to store count of each character appearance (Solution to follow-up question)

In this approach, we will use a temporary array to store each character count from input string s and compare character count against input string t or the other way around.

We will create a function usingArray that takes input arguments string s and t.
Base case is, if input strings s and t lengths are not same, then we can simply return false because these strings won't be anagrams of each other.
Create a temporary array with size as 26 if the characters going to be lowercase or uppercase english alphabet letters. (If the characters are going to be ASCII characters, then you can initialize array with 128 size)
Then, for each character in input string t add character count in correponding position.

int[] arr = new int[26]; for(int i=0; i<s.length(); i++) { arr[s.charAt(i) - 'a']++; }

Then, for each character in input string s, decrement the count from temporary array that we have created above.
- If the count at character position becomes -1, this means that the string is not an anagram.
- If the count at character position never becomes -1, then both strings are anagrams of each other.

public class ValidAnagram { /* Using a temporary array */ static boolean usingArray(String s, String t) { if(s.length() != t.length()) { return false; } int[] arr = new int[26]; for(int i=0; i<s.length(); i++) { arr[s.charAt(i) - 'a']++; } for(int j=0; j<t.length(); j++) { int charIndex = t.charAt(j) - 'a'; arr[charIndex] = arr[charIndex] - 1; if(arr[charIndex] == -1) { return false; } } return true; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string length.
Space complexity: O(1) since we are creating a temporary array with size 26 or 128 depends on characters type.

In this approach, we will use a HashMap to store each character count from input strings s and t and we store the count of characters of each string into a separate HashMap. Then, for each key in one HashMap check if the character count in other HashMap and see if they are same, if they are same then the strings are anagrams of each other, otherwise they are not anagrams.

This approach will work for any type of characters, ASCII or Unicode etc.

import java.util.HashMap; import java.util.Map.Entry; public class ValidAnagram { /* Using two hashmaps two keep character count of each string s and t */ static boolean usingTwoHashMap(String s, String t) { if(s.length() != t.length()) { // if the lengths are not same, they can't be anagrams return false; } HashMap<Character, Integer> s_count = new HashMap<>(); HashMap<Character, Integer> t_count = new HashMap<>(); for(int i=0; i<s.length(); i++) { s_count.merge(s.charAt(i), 1, Integer::sum); t_count.merge(t.charAt(i), 1, Integer::sum); } //now, for every character count in s_count, check if the count in t_count matches or not for(Entry<Character, Integer> charToCountEntry : s_count.entrySet()) { if(!charToCountEntry.getValue().equals(t_count.get(charToCountEntry.getKey()))) { return false; } } return true; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string length.
Space complexity: O(n) since we are storing character count into a HashMap.

This approach is same as solution 1, instead of using an array we will be using a HashMap, so that the solution will work for any type of characters that are in input strings like ASCII or Unicode etc.

import java.util.HashMap; public class ValidAnagram { /* Using a single HashMap - equivalent to using arrays approach*/ static boolean usingSingleHashMap(String s, String t) { if(s.length() != t.length()) { return false; } HashMap<Character, Integer> s_count = new HashMap<>(); for(int i=0; i<s.length(); i++) { s_count.merge(s.charAt(i), 1, Integer::sum); } for(int j=0; j<t.length(); j++) { int newValAfter = s_count.merge(t.charAt(j), -1, Integer::sum); // this returns the new value after decrementing the count if(newValAfter == -1) { return false; } } return true; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string length.
Space complexity: O(n) since we are storing character count into a HashMap.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis:

Complexity Analysis:

Complexity Analysis: