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

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;
}

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;

}

The Muddy Engineer