242. Valid Anagram

Demonstrates how we can leverage limited set of inputs and mapping technique to save on both space and time

Solution

We can solve this problem by using a array of size 26(alphabet size) with counts 0. We can traverse the first string s, find exact index in array of each char using (charCode - 97) and store the frequency of each character in a array. Then we can traverse the second string t and decrement the frequency of each character in the array. If the array contains only 0 values at the end, then the second string t is an anagram of the first string s.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length !== t.length) {
        // If the lengths are different, then t cannot be an anagram of s
        return false;
    }

    // Initialize a array with 0 frequencies for each character
    const freqTable = Array(26).fill(0);

    // Traverse the first string s and update the frequency table
    for (let i = 0; i < s.length; i++) {
        const charCode = s.charCodeAt(i) - 97;
        freqTable[charCode]++;
    }

    // Traverse the second string t and decrement the frequency table
    for (let i = 0; i < t.length; i++) {
        const charCode = t.charCodeAt(i) - 97;
        freqTable[charCode]--;

        if (freqTable[charCode] < 0) {
            // If the frequency goes below 0, then t cannot be an anagram of s
            return false;
        }
    }

    // If all frequencies are 0, then t is an anagram of s
    return true;
};

console.log(isAnagram("anagram", "nagaram"));   // Output: true
console.log(isAnagram("rat", "car"));   // Output: false

Time Complexity: O(n) where n is the length of the strings s and t. We traverse each string only once.
Space Complexity: O(1) since the array has a fixed size of 26 characters (assuming only lowercase letters are used in the strings).

1. Two Sum

This is a beginner problem which helps demonstrate how we can use hashmap and a little Math sense to take our time complexity from O(n^2) to O(n)

Solution:

We iterate over the array of integers and for each number, we check if its complement (target - number) already exists in the hash map. If it does, we have found a pair of numbers that add up to the target. If it doesn't, we can add the current number to the hash map and continue iterating.

function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

console.log(twoSum([3,2,4], 6)) //outputs [1, 2]

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the length of the array of integers nums. This is because we traverse the array only once.

Space Complexity:

The space complexity of the above algorithm is O(n), because we store at most n key-value pairs in the hash map.

205. Isomorphic Strings

This is a beginner problem demonstrating how intelligent mapping technique can be used to solve complex problems

Solution:

To solve this problem, we need to find a way to map each character in s to a character in t. We can do this by using two hash maps - one to map characters from s to t, and another to map characters from t to s.

We iterate over each character in s and t, and for each character, we check if it has been mapped before. If it has been mapped before, we check if the mapping is the same in both s and t. If it is not, we return false. If the character has not been mapped before, we add it to the hash map.

We return true if all characters have been checked and the condition is satisfied.

const isIsomorphic = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const mapST = {};
    const mapTS = {};

    for (let i = 0; i < s.length; i++) {
        const charS = s[i];
        const charT = t[i];

        if (mapST[charS] !== undefined && mapST[charS] !== charT) {
            return false;
        }

        if (mapTS[charT] !== undefined && mapTS[charT] !== charS) {
            return false;
        }

        mapST[charS] = charT;
        mapTS[charT] = charS;
    }

    return true;
};

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input strings s and t. We iterate over each character in s and t only once.

Space Complexity:

The space complexity of this solution is also O(n), where n is the length of the input strings s and t. We create two hash maps to store the mappings between characters from s to t and from t to s. The maximum size of these hash maps is n.