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