Ransom note

Can the ransom note be built using only the letters available in the magazine? Count, then spend.

Time O(m + n)Space O(1)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Count every letter available in the magazine once. Then walk the ransom note and spend one copy of each letter it needs. If a letter is ever missing, or every copy has already been spent, the note cannot be built.

Code

public static bool CanConstruct(string note, string magazine) {
    var letters = new Dictionary<char, int>();
    foreach (char c in magazine) letters[c] = letters.GetValueOrDefault(c) + 1;
    foreach (char c in note) {
        if (!letters.TryGetValue(c, out int n) || n == 0) return false;
        letters[c] = n - 1;
    }
    return true;
}

Tips

GetValueOrDefault(c) treats a letter not yet seen as zero, so counting is one line.
This is the same counting pattern as Valid Anagram, just with two different-length strings and spending happening in only one direction.

In the .NET library

Because only subtraction happens while reading the note, never addition, a letter count can only reach zero and then fail - the explicit n == 0 check is what catches a letter that has already been fully spent.