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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
using namespace std; typedef vector<pair<int, string>> library_t; typedef unordered_map<string, int> map_t; //Forward declaration int checkForChain(const string s, const map_t& wordMap); /* * Complete the function below. */ int longest_chain(vector < string > w) { if (w.empty()) { return 0; } int n = w.size(); //Size of library //Sorted library, which is an array of pairs. Each pair consists of a word from the //input dictionary and its length. library_t wSorted; for (auto i = w.begin(); i != w.end(); ++i) { wSorted.push_back({(*i).size(), *i}); } //Sort library (containing input dictionary) by size, from shortest to longest sort(wSorted.begin(), wSorted.end()); //Use a map to keep track of all words in library //for faster lookup time. The key is the word, and the value //is the longest possible chain up to that word map_t wordMap; wordMap.insert({wSorted[0].second, 1}); //Keeps track of the longest chain up to a given word for dynamic programming. //An index i in chainLength corresponds to the same index in wSorted int chainLength[n]; int* chainLengthInit = chainLength; for (int i = 0; i < n; ++i) { *(++chainLengthInit) = 1; } int longestChain = 0; string s; int sSize; //Iterate through every word in wSorted and find the longest possible chain up //to that word. Also keep track of the overall longest possible chain for(int i = 0; i < n; ++i) { s = wSorted[i].second; int chainLen = checkForChain(s, wordMap); chainLength[i] = chainLen; longestChain = max(longestChain, chainLen); //Update map wordMap.insert({s, chainLen}); } return longestChain; } //For a single string s, checks for the longest possible chain with s at the //beginning. Returns an integer denoting the length of that chain int checkForChain(const string s, const map_t& wordMap) { int longestChain = 1; //Longest chain for s string shortStr; //Holds s with one letter removed int sSize = s.size(); /* Remove one letter from s and check if the new, shortened word exists in the library using the map. If it does, the length of the chain that can be made by removing this letter is 1 + the length of the chain of the new, shortened word. Repeat this for all possible letters and keep track of the longest possible chain */ for (int i = 0; i < sSize; ++i) { shortStr = s; shortStr.erase(shortStr.begin() + i); auto map_i = wordMap.find(shortStr); if (map_i != wordMap.end()) { //Length of chain made by removing this letter int len = map_i->second + 1; longestChain = max(longestChain, len); } } return longestChain; } |