Somewhat similar to https://leetcode.com/problems/longest-string-chain/

I didn't consider some edge cases. Like the input list has duplications. I think counting the frequency of each word at the beginning could solve this.

```
class Jewellery:
def jewelleryDesign(input):
input.sort(key=lambda x: -len(x))
res=0
hasSeen=set()
def dfs(word,length):
nonlocal res
if word:
res=max(res,length)
for char in "abcdefghijklmnopqrstuvwxyz ":
new_word=char+word[1:]
new_word=new_word.strip()
if new_word in input and new_word not in hasSeen:
hasSeen.add(new_word)
dfs(new_word,length+1)
for w in input:
dfs(w,0)
return res
a=['gbpy','sbpy','bpy','bmy']
print(Jewellery.jewelleryDesign(a))
```

Output is correct

This might work, this is basically LIS using strings

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll maxn=200000+20;
const ll mod=1e9+7;
const ll m2=1e9+7;
const ll INF64 = ld(1e18);
const ll max2=1e3+10;
const ll N = 501;
const ll MAXN=2e5+10;
const ll ALPHABET_SIZE = 2;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
bool compare(string s1,string s2)
{
return(s1.size()<s2.size());
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
//long long tt = clock();
#endif
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
cin>>n;
int i;
vector<string> v(n);
int sz=0;
set<string> s;
map<string,int> mp1,dp;
for(i=0;i<n;++i)
{cin>>v[i];
//sz=max(sz,v[i].size());
s.insert(v[i].substr(1,v[i].size()-1));
dp[v[i].substr(1,v[i].size()-1)]++;
mp1[v[i].substr(1,v[i].size()-1)]|=(1<<(v[i][0]-'a'));
}
vector<string> vf;
for(auto x:s)
vf.push_back(x);
sort(vf.begin(),vf.end(),compare);
int ans=0;
for(auto x:vf)
{if(x=="")
continue;
string sf=x.substr(1,sf.size()-1);
char c=x[0];
int x1=c-'a';
if(dp.count(sf)!=0)
{
if((mp1[sf]&(1<<x1))!=0)
{
dp[x]+=dp[sf];
ans=max(ans,dp[x]);
}
}
}
cout<<ans;
return(0);
}
```