After the Node cloning problem, this one looks like a piece of cake.

I quickly whipped up a solution in which I hash all the chars from both magazine and ransom but char count and then loop through all the chars in ransom, and if the char count in magazine is less than the char count in ransom for any given char, we know the magazine can't reproduce the ransom note.

Initial solution

function canConstruct(ransomNote: string, magazine: string): boolean {
    const ransomNoteHash: Record<string, number> = {}
    const magazineHash: Record<string, number> = {}
    ransomNote.split("").forEach(letter => {
        if (ransomNoteHash[letter]) {
            ransomNoteHash[letter] += 1
        }
        else {
            ransomNoteHash[letter] = 1
        }
    })
    magazine.split("").forEach(letter => {
        if (magazineHash[letter]) {
            magazineHash[letter] += 1
        }
        else {
            magazineHash[letter] = 1
        }
    })

    const ransomNoteKeys = Object.keys(ransomNoteHash);
    for (let i = 0; i < ransomNoteKeys.length; i++) {
        if (ransomNoteHash[ransomNoteKeys[i]] > (magazineHash[ransomNoteKeys[i]] || 0)) {
            return false
        }
    }
    return true
};

That said, upon running it, I see that I'm in the 7.8 percentile of runtime. Yikes.

An attempt at a different solution

My next thought is two use two pointers on the two arrays - ransom and magazine. Here are the steps I'm thinking -

1 - convert both strings to arrays and map each letter to its corresponding number

2 - sort both arrays

3 - walk through both arrays at once using Two Pointers. I'll move the pointer forward through both ransom and magazine until either magazine jumps to the next number before ransom does (failure case) or ransom jumps to the next number before magazine, at which point I'll progress the pointer in magazine until it is at that number. If the next number in magazine is higher than the number in ransom, that is also a failure case. 

const lettersToNumbers = {
    'a': 0,
    'b': 1,
    'c': 2,
    'd': 3,
    'e': 4,
    'f': 5,
    'g': 6,
    'h': 7,
    'i': 8,
    'j': 9,
    'k': 10,
    'l': 11,
    'm': 12,
    'n': 13,
    'o': 14,
    'p': 15,
    'q': 16,
    'r': 17,
    's': 18,
    't': 19,
    'u': 20,
    'v': 21,
    'w': 22,
    'x': 23,
    'y': 24,
    'z': 25,
};

function canConstruct(ransomNote: string, magazine: string): boolean {
    const convertStringToSortedNumberArray = (input: string) => {
        return input.split("").map(letter => lettersToNumbers[letter]).sort()
    }
    const ransomNums = convertStringToSortedNumberArray(ransomNote);
    const magazineNums = convertStringToSortedNumberArray(magazine);
    console.log({
        magazineNums,
        ransomNums
    })
    let magazinePointer = 0;
    for (let i = 0; i < ransomNums.length; i++) {
        const ransomVal = ransomNums[i];
       
        while (
            magazineNums[magazinePointer] < ransomVal && magazinePointer < magazineNums.length) {
                console.log({
                    mag:  magazineNums[magazinePointer],
                    ransomVal
                })
            magazinePointer = magazinePointer + 1
            }
        if (magazineNums[magazinePointer] > ransomVal) {
            return false
        }
        magazinePointer = magazinePointer + 1
    }
    if(magazinePointer > magazineNums.length){
        return false
    }
    return true
};

Lolllll, this ran even slower, though I think it was a fun solution to implement.

My optimized solution

I realized my first solution was closer to the proper answer, but I had a major inefficiency. In my original solution I made hashes of both the ransom and the magazine and then compared the ransom hash to the magazine hash. A more efficient way of doing it is to create the magazine hash and then step through the ransom numbers and decrement the magazine hash until the ransom is done (success case) or I no longer have a letter that the ransom needs (failure case). 

function canConstruct(ransomNote: string, magazine: string): boolean {
    const magazineHash: Record<string, number> = {}

    magazine.split("").forEach(letter => {
        if (magazineHash[letter]) {
            magazineHash[letter] += 1
        }
        else {
            magazineHash[letter] = 1
        }
    })

    const ransomLetters = ransomNote.split("");

    for (let i = 0; i < ransomLetters.length; i++) {
        if(!magazineHash[ransomLetters[i]]){
            return false;
        }
        magazineHash[ransomLetters[i]] = magazineHash[ransomLetters[i]] - 1
    }
    return true
};

This ran in the 80th percentile of runtimes. Its big O would be O(M+R) with M and R representing the magazine and the ransom note lengths.

Parting throughts

  • It was refreshing to land on an easy problem I could immediately answer, even if my original solution was inefficient.

  • It's important to keep in mind the number of times I'm iterating through things. Sometimes it's overkill and does nothing but slow down the solution.