Longest Chain DP

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 a ..

More about this question can be found here.

https://blog.cancobanoglu.net/2016/09/18/interview-questions-string-chain/

C++ reference code

https://www.careercup.com/question?id=5734224617275392

#include <bits/stdc++.h>

using namespace std;

const int maxn=10000;

unordered_map< string,int > hashTable;
int dp[maxn];

int LongestChain(vector<string> V)
{

	vector< pair<int,string> > list;
	for (auto s:V){
		list.push_back({s.size(),s});
	}
	sort(list.begin(),list.end());
	
	int N=list.size();
	hashTable.insert( {list[0].second,0} );
	dp[0]=1;

	int answer=dp[0];

	for (int i=1;i<N;i++){
		dp[i]=1;
		string s=list[i].second;
		
		int size = s.size();
		for (int j=0;j<size;j++){
			
			string tmpStr = s;
			tmpStr.erase(tmpStr.begin()+j);
			auto it = hashTable.find(tmpStr);

			if (it!=hashTable.end())
				dp[i] = max (dp[i],dp[it->second]+1);
		}
		answer = max ( answer , dp[i]);

		hashTable.insert({s,i});

	}

	return answer;
}



int main()
{

	int N;
	cin >> N;
	vector<string> V(N);
	for (int i=0;i<N;i++)
		cin >> V[i];

	cout << LongestChain(V) << endl;


	return 0;
}

I have a python version code for reference.

def longest_chain(words):
    words.sort(key=len)
    dp = {w:1 for w in words}
    for w in words:
        if len(w)==1:continue
        this_res = 1
        for i,c in enumerate(w):
            new_w = w[:i]+w[i+1:]
            if new_w in dp:
                this_res = max(this_res, dp[new_w]+1)
        dp[w] = this_res
    return max(dp.values())
words = ["a", "b", "ba", "bca", "bda", "bdca"]
print(longest_chain(words))

The problem above is similar to this problem

1048. Longest String Chain

Longest String Chain - LeetCode

Naive solution (1000 + ms)

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words = list(set(words))
        db = collections.defaultdict(list)
        for w in words:
            db[len(w)].append(w)
        res = 0
        lns = sorted(list(set(db.keys())))
        #print(lns)
        memo = {}
        def valid(a, b):
            a_c = collections.Counter(a)
            b_c =  collections.Counter(b)
            extra = 1
            for k in a_c:
                if b_c[k]==a_c[k]:
                    continue
                elif b_c[k]==a_c[k]+1 and extra==1:
                    extra = 0
                else:
                    return False
            return True
        def get_depth(w):
            if w in memo:return memo[w]
            if len(w) == max(lns):
                memo[w]=1
                return 1
            else:
                this_res = 1
                for w_next in db[len(w)+1]:
                    if valid(w, w_next):
                        temp_res = 1+get_depth(w_next)
                        this_res = max(this_res, temp_res)
                memo[w] = this_res
                return this_res
                
            
        return max([get_depth(w) for w in words])

or another naive way (2000 ms)

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        dp = {}
        cnt = collections.defaultdict(list)
        for w in words:
            cnt[len(w)].append(w)
        keys = sorted(cnt.keys())
        for w in cnt[keys[0]]:
            dp[w] = 1
        def match(w1, w2):
            cnt1 =  collections.Counter(w1)
            cnt2 = collections.Counter(w2)
            return sum(abs(cnt2[key]-cnt1[key]) for key in (set(cnt1) | set(cnt2))) == 1
        for key in keys[1:]:
            if key-1 not in cnt:
                for w in cnt[key]:
                    dp[w] = 1
            else:
                for cur_w in cnt[key]:
                    this_res = max([dp[pre_w]+1 for pre_w in cnt[key-1] if match(pre_w, cur_w)] or [1])
                    dp[cur_w]= this_res
        return max(dp.values())

DP (142 ms)

https://leetcode.com/problems/longest-string-chain/discuss/294890/C++JavaPython-DP-Solution

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        dp = {}
        for w in sorted(words, key=len):
            dp[w] = max(dp.get(w[:i] + w[i + 1:], 0) + 1 for i in range(len(w)))
        return max(dp.values())

820. Short Encoding of Words

https://leetcode.com/problems/short-encoding-of-words/

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        d = set()
        res = 0
        for w in sorted(words, key=len, reverse=True):
            #print(d)
            if w[::-1] in d:
                continue
            else:
                res+=len(w)+1
            ww = w[::-1]
            for i in range(1,len(ww)+1):
                d.add(ww[:i])
        return res