Longest Character Removal Chain Programming Problem - C++ Solution

Home / Longest Character Removal Chain Programming Problem - C++ Solution

The following presents my solution for the Longest Chain of Character Removals problem.

Problem Statement

You are given a library with n words (w[0], w[1], ...,w[n-1]). You choose a word from it, and in each step, remove one letter from this word only if doing so yields another word in the library. What is the longest possible chain of these removal steps?

Constraints:

  • 1 <= n <= 50000
  • 1 <= the length of each string in w <= 50
  • Each string is composed of lowercase ascii letters only

The function should take in an array of strings w as its argument and should return a single integer representing the length of the longest chain of character removals possible.

Example input/output

a
b
ba
bca
bda
bdca

Calling the function on the input above should output 4. The longest possible chain is "bdca" -> "bca" -> "ba" -> "a".

Solution

I solved this problem using dynamic programming (DP):

1. Sort the input dictionary by size, from shortest to longest
2. Create a dynamic programming table, which I call chainLength of size n. Define chainLength[i] to be the length of the longest chain of character removals that can be formed starting with w[i] in the sorted input dictionary.
3. Use an unordered_map (hash table) to keep track of words in the input dictionary that have already been processed by the DP algorithm. The key value is the word from the input dictionary and the mapped value is the longest possible chain starting with that word (same value as stored in the DP table)
4. Iterate through every word in the sorted input dictionary and find the longest possible chain up to that word. In other words, fill up from DP table going from index 0 to n-1.
5. To calculate chainLength[i] in the dynamic programming table, iterate through each letter of w[i] and check if removing that letter would yield another word in the dictionary. This can be done in constant time using the hash table. If removing a letter from w[i] yields w[j], then it is possible to create a chain with length 1 + chainLength[j]. (Note that in this scenario j will always be less than i because the input is sorted by length and so the DP algorithm will process the shorter words first) By doing this for every letter, we can find the longest possible chain starting with w[i].
5. The result is the maximum value in the dynamic programming table chainLength

Code

Leave a Reply

Your email address will not be published. Required fields are marked *