JSFiddle - React, Tailwind, and code Playground

by jayakrishnancn

TypeScript

function isPredecessor(a, b) {

  a = a.split("");
  b = b.split("");

  if (a.length !== b.length - 1) {
    return false;
  }
 
 let map = {}

	let l = 0, r= 0, foundFirst= false;

	while(l < a.length && r < b.length){
		
    if(a[l] === b[r]){
	    l++; r++;
    	continue;
    }
 
 		if(foundFirst){
	    return false;
    }
    
    foundFirst = true;
    
    if(a[l] === b[r+1]){
    	r++;
    }
    else{
    	l++;
    }
    
    
  }
  
  
  return l == a.length && r === b.length 
	
  
  
}


function longestStrChain(words: string[]): number {
  
  let memo = [];
  const n = words.length; /// 6
  
  words.sort((a,b) =>{ 
  	return  a.length - b.length;
  }) 
  function dp(index) {

    if (index === n) return 0;
    if (index === n - 1) return 1;

    if (memo[index]) return memo[index];

    let max = 1;

    let word1 = words[index];
	
    for (let i = index+1; i < n; i++) {
		 
      const is = isPredecessor(word1, words[i])
       
      if (is) {
        max = Math.max(max, dp(i) +1 );
        
      }
			 
    }

    memo[index] = max;
    return max;

  }
  let max = 0;
  for(let i=0;i<n;i++){
  	max = Math.max(max, dp(i));
  }
	return max;

};
let res = longestStrChain(["kss","czvh","zczpzvdhx","zczpzvh","zczpzvhx","zcpzvh","zczvh"]);
console.log(res)