Problem 55: Longest String Chain
Problem Statement: Given a list of words, a word chain is a sequence of words such that each word is formed by removing exactly one letter from its previous word. Find the length of the longest such chain.
Input
The first line contains an integer n. Each of the next n lines contains a word consisting of lowercase letters.
Output
Print the length of the longest string chain.
Examples
Input:
5
abcd
abc
abd
ab
a
Output:
4
Solution Explanation
Sort words by length. Use dynamic programming where for each word, try removing each letter and check if the resulting word exists. Update dp[word] = max(dp[predecessor] + 1).
Solution in C++
#include
#include
#include
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector words(n);
for(auto &w : words)
cin >> w;
sort(words.begin(), words.end(), [](const string &a, const string &b){ return a.size() < b.size(); });
unordered_map dp;
int ans = 0;
for(auto &word : words){
dp[word] = 1;
for(int i = 0; i < word.size(); i++){
string pred = word.substr(0, i) + word.substr(i + 1);
if(dp.find(pred) != dp.end()){
dp[word] = max(dp[word], dp[pred] + 1);
}
}
ans = max(ans, dp[word]);
}
cout << ans << "\n";
return 0;
}