DP 45. Longest String Chain | Longest Increasing Subsequence | LIS

Please watch the video at 1.25x for a better experience.

a

In this video, we solve the Longest String Chain, prior to this please solve dp 41 and dp 42.

[manasgupta]

in checkPossible method, add condition if(j<s2.length() && s1.charAt(i)==s2.charAt(j)), otherwise it fails for s1="xx" and s2="x"

[aloklaha]

Learnt how to check for subsequence using two pointers.

[ToonTorque]

In case anyone is struggling with the java code here it is
here i have did this one on leetcode and its working as the maxi is returning the length of the array so i started it from 0 and added 1 in the end for the correct length

static int lSC(String[] arr){
Arrays.sort(arr,
int n = arr.length;
int[] dp = new int[n];
int maxi = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (checkPossible(arr[i], arr[j]) && 1 + dp[j] > dp[i]){
dp[i] = 1+ dp[j];
}
}
if (dp[i] > maxi){
maxi = dp[i];
}
}
return maxi + 1;
}

private static boolean checkPossible(String s, String s1) {
if (s.length() != s1.length()+1){
return false;
}
int first = 0;
int second = 0;

while (first < s.length()){
if (second < s1.length() && s.charAt(first) == s1.charAt(second)){
first++;
second++;
}
else {
first++;
}
}
if (first == s.length() && second == s1.length()){
return true;
}
else return false;
}

[JayPatel-snit]

What an amazing thought process. I haven't seen anywhere yet.

[dennyage]

Checkboolean() function will throw out of index error when S1: abcd, S2: abc

[aaravarya]

Bro make some videos on game theory, it's highly needed!! Couldn't find any better content on yt.

[cinime]

Understood! Thank you much as always!!

[amitkulkarni]

solved this without watching because of Striver !!!

[ritikshandilya]

keeping the idea simple and building up the solution is a rare art only our Savior Striver possesses . Thankyou for amazing solution Striver

[satendra]

in c++ your comp function should be static since sort() is static .(if code is in class)

[satyamgupta]

you can also check the both Strings by using lcs and if len(lcs) == smaller string then it is true else false.
class Solution {
public boolean isValid(String s, String t)
{
int n=s.length();
int m= t.length();
if(n-m!=1) return false;
int[][] dp=new int[n+1][m+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{

dp[i][j]=1+dp[i-1][j-1];
else
dp[i][j]=Math.max(dp[i][j-1], dp[i-1][j]);
}
}
if(dp[n][m]==t.length()) return true;
return false;
}
public int longestStrChain(String[] words) {
int maxi=-1;
int[] dp=new int[words.length];
Arrays.fill(dp, 1);

Arrays.sort(words, new Comparator<>(){
public int compare(String a, String b)
{
return a.length()-b.length();
}
});
for(int i=0;i<words.length;i++)
{
for(int prev=0;prev<i;prev++)
{
if(isValid(words[i], words[prev]))
{
dp[i]=Math.max(dp[i], 1+dp[prev]);
}
}
if(dp[i]>maxi)
maxi=dp[i];
}
return maxi;
}
}
It indeed takes a bit more time but as a another solution.

[dhairyachauhan]

another complex way of solving it using recursion(c++)

#include <bits/stdc++.h>

bool compare(string &s1, string &s2)
{
return s1.size() < s2.size();
}

int lcs(string &s, string &t, int idx1, int idx2){
if(idx1 < 0 || idx2 < 0){
return 0;
}

if(s[idx1] == t[idx2]){
int pick = 1+lcs(s, t, idx1-1, idx2-1);
return pick;
}
return max(lcs(s, t, idx1-1, idx2), lcs(s, t, idx1, idx2-1));
}

int solve(vector<string>&arr, int idx, int n, int prev_idx){
if(idx == n){
return 0;
}

if(prev_idx == -1 || (arr[idx].length()-lcs(arr[idx], arr[prev_idx], arr[idx].length()-1, arr[prev_idx].length()-1) == 1 && arr[idx].length() == 1 + arr[prev_idx].length())){
int pick = 1 + solve(arr, idx+1, n, idx);
int dontpick = solve(arr, idx+1, n, prev_idx);
return max(pick, dontpick);
}
return solve(arr, idx+1, n, prev_idx);
}

int &arr)
{
sort(arr.begin(), arr.end(), compare);
int n = arr.size();
return solve(arr, 0, n, -1);

}

[studyonline]

Another way of doing - using Recursion (top-down)
No need to sort as we try out all possibilities.

Take any word from the list ["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]
Ex - pcxbcf
try to generate all substrings of it by deleting one character at a time(as the predecessor is one length less than the current word) and check if it is in the given list.

cxbcf
pxbcf
pcbcf
pcxcf
pcxbf
pcxbc

If the generated substrings are in the list, you can continue with the process else, go with the next substring. Repeat this process for all the words in the given list and return the max length.

words=["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]
seen=set(words)

def f(s):
if len(s)==1:
return 1 if s in seen else 0
ans=0
for i in range(len(s)):
sub=s[0:i]+s[i+1:]
if sub in seen: ans=max(ans, f(sub))
return 1+ans

ans=0
for word in words:
ans=max(ans, f(word))
return ans


As you can see there are overlapping sub-problems in it --> For the substrings cxbcf and pxbcf (and others) we are calculating the results for xbcf >1 time, So you can easily memoize the solution.

[Thescienceworld]

Now, i feel so much confidance . i applied same exact code and i came just to see your stretegy. 😃

[yashkumarsinghpatwa]

checkPossible method should return false when s1 = "aa" and s2 = "aa". But currently it returns true

[ratinderpalsingh]

Understood, sir. Thank you very much.

[codingachinilgtifirbhikrrh]

For C++ add this condition in the compare function in the end:
else if(j == word2.size())
return 1;
and also make the custom comparator function static

[tasneemayham]

Striver, I have a question: for Time Complexity when do you know when to multiply the length by N^2 and when to just add it. In the last problem you added it, but here you multiplied it. May anyone who can help tell me the intuition here? and thx.
Of course THANK YOU STRIVERRR. You are the best bhaiya!!

[saurabhsangam]

Python solution:

def isPredecessor(strI, strPrev):
if len(strI) != (len(strPrev) + 1): return False
p1 = p2 = 0

while p1 < len(strI):
if p2 < len(strPrev) and strI[p1] == strPrev[p2]:
p2 += 1
p1 += 1

return p1 == len(strI) and p2 == len(strPrev)

class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len)
ans, n = 1, len(words)
dp = [1] * n

for i in range(n):
for prev in range(i):
if isPredecessor(words[i], words[prev]):
dp[i] = max(dp[i], dp[prev] + 1)
ans = max(ans, dp[i])

return ans

[balabala]

is it possible to solve this by tabulation approach, or memorization approach