Coding Interview Questions | Ransom Note

December 27th, 2023

Ransom Note Problem Introduction:

This summary will talk about my solution to the ransom note problem as seen on leetcode here.

Ransom Note Solution:

function canConstruct(ransomNote: string, magazine: string): boolean {
  const magazineNoteLetterMap = new Map<string, number>();

  for (const magazineLetter of magazine) {
    magazineNoteLetterMap.set(
      magazineLetter,
      (magazineNoteLetterMap.get(magazineLetter) ?? 0) + 1
    );
  }

  for (const ransomLetter of ransomNote) {
    const currentMagazineNoteLetterCount =
      magazineNoteLetterMap.get(ransomLetter);
    if (!currentMagazineNoteLetterCount) {
      return false;
    }

    magazineNoteLetterMap.set(ransomLetter, currentMagazineNoteLetterCount - 1);
  }

  return true;
}

Ransom Note Solution Summary:

1. Initializing the map: The solution above utilizes a Map to count occurrences of each letter in the magazine.
2. Ransom note iteration: We then iterate through the ransomNote, checking if each required letter is present in the magazine and has a sufficient count.
3. Early return: If a required letter is missing or its count is exhausted, we return false; otherwise, return true.
4. Efficiency: This approach ensures that each letter in the magazine is used at most once in constructing the ransomNote.

Overall, the time complexity of the solution is O(m), where m is the magazine string length given we’ll check at most m characters in the ransom note string and return early if the all magazine characters have exhausted their counts in the map when iterating through the ransom note string. The space complexity of the solution is O(1) as there are at most 26 letters in the alphabet, effectively meaning the map used to the store the character counts is of constant space.