242. Valid Anagram

Difficulty: Easy

Question: 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 * 104
• s and t consist of lowercase English letters.

Approach:

To determine if two strings are anagrams, we need to check whether they have the same characters with the same frequency. We can break this problem down into steps for our code solution.

1. First, compare the lengths of strings s and t. If they are not equal, they can’t be anagrams (anagrams have same length of chars), so return false.
2. Initialize a Map to store the characters and count the frequency of each char in the string s.
3. Iterate through the string s, and for each character:
   • Check if the character is already in the Map
     • If it’s not in the Map, add it with a count of 1.
     • If it’s already in the Map, increment its count by 1.
4. Next create a new loop and tierate through the string t, and for each character:
   • Check if the character exits in the Map.
     • If it does, decrement its count by 1.
5. After both loops, iterate through the values in the Map.
   • If any character’s count is greater than 0, return false, as it means there is a character in s that doesn’t have corresponding characters in t.
6. If all characters in t are accounted for, return true
   

Javascript Solution:

var isAnagram = function(s, t) {
    if(s.length !== t.length) return false
    let map = new Map()
    for(let i = 0; i < s.length; i++){
        if(!map.has(s[i]))
            map.set(s[i], 1)
        else {
            map.set(s[i], map.get(s[i])+1)
        }
    }
    for(let j = 0; j < t.length; j++){
        if(map.has(t[j]))
            map.set(t[j], map.get(t[j])- 1)
    }

    for(let i of map.values()) {

    
        if(i > 0) return false
    }
    return true
};

Time Complexity

Time complexity of the provided solution is O(n), where n is the length of the longer of the two input strings

1. The first loop iterates through the characters of the string s and populates the map with quantity of each character.
   • The loop runs in O(n) time , where “n” is the length of string s
2. The second loop iterates through the characters of string t and upates the character frequencies in the map.
   • This loop also runs in O(n) time, where n is the length of string t
3. The third loop iterates through the values in the map to check if any character quantities are greater then 0.
   • This loop takes O(k) time. where k is the number of distinct characters in both strings.
     • in the worst case k can be considered constant because the number of distinct characters in the alphabet is limited.

Overall, the time complexity is dominated by toe two loops that iterate the strings, both of which are O(n)

Space Complexity

The space complexity of the solution is O(k),

k represents the number of distinct characters in both input strings s and t. The space complexity is determined by the size of the map, which is directly related to the number of distinct characters in both input strings.

In most practical cases k is relatively small compared to the length of the strings, so the space complexity can be considered as O(1), However in worst case when all possible distinct characters are present it would be O(k)

I plan to do breakdowns of leetcode problems when ever I have free time!