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
andt
:- return
true
, ift
is an anagram ofs
- return
false
otherwise.
- return
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
andt
, 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, andfalse
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
andt
. This is because the code usesArrays.sort()
to sort the character arrayssc
andtc
. - 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
andt
. - This is because the code creates two character arrays,
sc
andtc
, 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
andcount2
are used to count the number of characters in the given two stringss
andt
respectively. - The function
count()
is used to traverse the given string, calculate the number of occurrences of a character and store them in thecount
HashMap and return it. - Finally,
count1
andcount2
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 stringss
andt
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
andcount2
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 thealphabet
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 Strings
in the first iteration. - And then decrement the values of the same
alphabet
array with stringt
in the second iteration. - In both iterations, we perform the operations
s.charAt(i) - 'a'
andt.charAt(i) - 'a'
. Here, the characters of the strings
and stringt
are subtracted with the character‘a’
to get an integer value of the letters that correspond to thealphabet
array.
- We increment the
- 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 returntrue
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
andt
. 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 stringt
. Finally, there is a third loop that checks if any count in thealphabet
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
Recommended Resources to Learn Data Structures and Algorithms
Basics of DS Algo Blogs:
Recommended YouTubers for LeetCode Problems:
1. NeetCode
Free Resources for Learning Data Structures and Algorithms:
Recommended Courses for Learning Data Structures and Algorithms:
- NeetCode Courses
- ZTM: Mastering the Coding Interview (Big Tech): Available on Udemy and ZTM Academy
- ZTM: Mastering the Coding Interview: Available on Udemy and ZTM Academy
- Data Structures & Algorithms, Level-up for Coding Interviews Course
- Striver’s A2Z (Free) Course
Top Coursera Courses for Learning Data Structures and Algorithms:
- Coding Interview Preparation (Meta)
- Algorithms Course Part I (Princeton University)
- Algorithms Course Part II (Princeton University)
- Data Structures and Algorithms Specialization (UC San Diego)
- 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 🙂.
Top comments (0)