I recently watched this thoroughly entertaining video by ThePrimeagen (aka Michael Paulson) where he pretended to solve algorithm questions on Leetcode as a job interview. He solved 6 problems in incremental difficulty, and when he got to the final problem I paused the video and tried to solve it myself.

1255. Maximum Score Words Formed by Letters

Given a list of words, list of single letters (might be repeating) and score of every character. Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times). It is not necessary to use all characters in letters and each letter can only be used once. Score of letters ‘a’, ‘b’, ‘c’, … ,’z’ is given by score[0], score[1], … , score[25] respectively.

Input: words = [“dog”,”cat”,”dad”,”good”], letters = [“a”,”a”,”c”,”d”,”d”,”d”,”g”,”o”,”o”], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation: Score a=1, c=9, d=5, g=3, o=2 Given letters, we can form the words “dad” (5+1+5) and “good” (3+2+2+5) with a score of 23. Words “dad” and “dog” only get a score of 21.

I have not done these types of algorithm questions in a few years, so it was a fun challenge although I was definitely quite rusty. I started off doing a recursive implementation which iterates through all the combinations of words and calculates the score. Basically at each iteration you calculate the maximum score with and without the word included. This works, but doesn’t count as a correct answer since you exceed to time limit for some of the test cases.

def score_for_word(word, letters_map, scores)
  unused_letters_map = letters_map.dup
  total_score = 0

  word.each_char do |char|
    if unused_letters_map[char].to_i >= 1
      unused_letters_map[char] -= 1
      total_score += scores[char.ord - 'a'.ord]
    else
      return [0, letters_map]
    end
  end

  [total_score, unused_letters_map]
end

def calculate_max_score_words(words, letters_map, scores, pick)
  return 0 if pick == words.size

  sfw, leftover_letters_map = score_for_word(words[pick], letters_map, scores)
  score_with_pick = 0
  if sfw > 0
    score_with_pick = sfw + calculate_max_score_words(words, leftover_letters_map, scores, pick + 1)
  end
  score_without_pick = calculate_max_score_words(words, letters_map, scores, pick + 1)

  [score_with_pick, score_without_pick].max
end

def max_score_words(words, letters, scores)
  letters_count = letters.inject({}) do |map, letter|
    map[letter] ||= 0
    map[letter] += 1
    map
  end

  calculate_max_score_words(words, letters_count, scores, 0)
end

This is a variation of the knapsack problem, which seems to show up in interview problems quite often, although I don’t think I have ever encountered it in a real world situation. The tricky part with this variation is that you need to keep track of the letters leftover at every step - which means you can’t use memoization. Or at least, I felt pretty strongly that you can’t use memoization because intuitively I felt that state of the subproblems don’t overlap. I proved this out by caching each state and logging when I get a cache hit. I never got a cache hit, so I was convinced that I was right.

def score_for_word(word, letters_map, scores, saved_answers)
  save_key = "#{word}=#{letters_map.map { |key, value| "#{key}:#{value}" }.join("|")}"

  unless saved_answers.key?(save_key)
    unused_letters_map = letters_map.dup
    total_score = 0

    word.each_char do |char|
      if unused_letters_map[char].to_i >= 1
        unused_letters_map[char] -= 1
        total_score += scores[char.ord - 'a'.ord]
      else
        return [0, letters_map]
      end
    end

    saved_answers[save_key] = [total_score, unused_letters_map]
  end

  saved_answers[save_key]
end

The actual cache keys end up looking like this:

eedc=a:8|b:2|c:7|d:2|e:3
eedc=a:8|b:2|c:7|d:2|e:4
eedc=a:8|b:2|c:7|d:3|e:4
eedc=a:8|b:2|c:7|d:3|e:5
eedc=a:8|b:2|c:7|d:4|e:4
eedc=a:8|b:2|c:7|d:4|e:5
eedc=a:8|b:3|c:7|d:1|e:5
eedc=a:8|b:3|c:7|d:1|e:6
eedc=a:8|b:3|c:7|d:2|e:5
eedc=a:8|b:3|c:7|d:2|e:6
eedc=a:8|b:3|c:7|d:3|e:3
eedc=a:8|b:3|c:7|d:3|e:4
eedc=a:8|b:3|c:7|d:3|e:6
eedc=a:8|b:3|c:7|d:3|e:7
eedc=a:8|b:3|c:7|d:4|e:3
eedc=a:8|b:3|c:7|d:4|e:4

Side note - I checked this with ChatGPT and the AI simply wouldn’t give up on memoization for the solution, it kept iterating over the same solution even though I’m pretty convinced it doesn’t work. (Maybe I’m wrong - feel free to enlighten me in the comments.)

Memoization is one way to implement dynamic programming, but the other way is to use tabulation. For some reason my mind usually goes to the top-down solution (memoization) first, but in this problem it seems like tabulation (the bottom-up solution) is a better (or possibly the only) solution. This also meant I had to re-familiarize myself with doing bitwise operations in Ruby.

I’ve seen tabulation examples done both as a one-dimensional or as a two-dimensional array - for some reason I found it easier to reason about as a one dimensional array. My understanding is that there shouldn’t be a performance difference between the two approaches - either in terms of time or memory usage.

I basically created an array to hold all the possible states - meaning 2^n states where n is the number of words - and then I had to figure out what the previous state was that you could use. So in the example given in the question - ["dog","cat","dad","good"] with letters ["a","a","c","d","d","d","g","o","o"] if you are trying to calculate the state for ["dog", "cat", "dad"] you would look back at the state of ["dog", "cat"] (which contains both the score and the remaining letters) and then see if you can form the word “dad” with the remaining letters. At least, that’s how I thought about it and it helped me iterate towards the solution.

def remove_most_significant_bit(num)
  return 0 if num == 0
  msb = 1 << Math.log2(num).floor
  num - msb
end

def score_for_word(word_frequencies, letter_frequencies, scores)
  unused_letters_frequencies = letter_frequencies.dup
  total_score = 0

  0.upto(25) do |index|
    if unused_letters_frequencies[index] >= word_frequencies[index]
      unused_letters_frequencies[index] -= word_frequencies[index]
      total_score += scores[index] * word_frequencies[index]
    else
      return [nil, letter_frequencies]
    end
  end

  [total_score, unused_letters_frequencies]
end

def max_score_words(words, letters, scores)
  word_frequencies = words.map do |word|
    Array.new(26,0).tap do |mask|
      word.each_char { |char| mask[char.ord - 'a'.ord] += 1 }
    end
  end

  letter_frequencies = Array.new(26, 0)
  letters.each do |char|
    letter_frequencies[char.ord - 'a'.ord] += 1
  end

  saved_scores = Array.new(2.pow(words.size-1))
  saved_letters = Array.new(2.pow(words.size-1))
  0.upto(2.pow(words.size) - 1) do |mask|
    if mask == 0
      saved_scores[mask] = 0
      saved_letters[mask] = letter_frequencies
    else
      lookback_index = remove_most_significant_bit(mask)
      added_word_frequency = word_frequencies[Math.log2(mask + 1).ceil - 1]

      if saved_scores[lookback_index] == nil
        saved_scores[mask] = nil
      else
        score, new_letter_frequencies = score_for_word(added_word_frequency, saved_letters[lookback_index], scores)
        saved_scores[mask] = score.nil? ? nil : score + saved_scores[lookback_index]
        saved_letters[mask] = new_letter_frequencies
      end
    end
  end

  saved_scores.reject(&:nil?).max
end

The part where I really got stuck was figuring out what word was being added in the ‘current state’ that was not present in the ‘lookback state’ - which is Math.log2(index + 1).ceil - 1 - that part kept feeling like there was an intuitive mathematical solution to it.

I have lots of mixed feelings about algorithm questions like these. I am under no illusion that I would have been able to solve this in an interview setting - if that was the expectation. I also don’t think that is a reasonable expectation since it’s not something most programmers deal with on a daily basis. However, it’s definitely important to understand these concepts so you know to look for that tool when you are in a situation that requires it. I was pleasantly surprised to find that this exercise brought back some of the magic that made me choose programming as a career - seeing how the brute force solution (even though it’s cleanly written and uses recursion) is orders of magnitude slower is really… cool. I even remember really enjoying the algorithm courses in college - but the setting there was very different since it was a take-home assignment to implement the algorithm. I remember seeing quicksort explained the first time and just getting excited about solving problems with elegant solutions like these - so it’s definitely fun going back and revisiting that.

Share on: Twitter, Facebook, Google+ or use the Permalink