DP 45. Longest String Chain | Longest Increasing Subsequence | LIS
Вставка
- Опубліковано 5 лют 2025
- Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: bit.ly/3KHsl9J
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/take...
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the Longest String Chain, prior to this please solve dp 41 and dp 42.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.o...
You can also get in touch with me at my social handles: linktr.ee/take...
in checkPossible method, add condition if(j
yep
bool isPossible(string &s1, string &s2){
if(s1.size()!=s2.size()+1) return false;
int i=0,j=0;
while(i
It didn't fail for me, simply goes to else condition, when j breaches s2.
UNDERSTOOD.........Thank You So Much for this_wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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, Comparator.comparingInt(String::length));
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;
}
but why you have not filled dp array with 1 and do the standarad lis ? why it giving error?
What an amazing thought process. I haven't seen anywhere yet.
Checkboolean() function will throw out of index error when S1: abcd , S2: abc
we can add if(second==s2.size()) return true; ,in the while loop
if (i == n or i == n-1) and j == m:
return True
return False
use above syntax
s1 will always be smaller than s2, as array is sorted
Bro make some videos on game theory, it's highly needed!! Couldn't find any better content on yt.
I have made few game theory videos, you could check them also, I hope that would help for time being , but would love to see videos by striver :)
As always "understood" ❤️
Understood! Thank you veeeeeery much as always!!
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
this will give tle
This solution will have more TC and SC
@@ayushgupta80 This will not get TLE for this particular problem as maximum size of the words[I] is 16. it will have larger TC = O(16*16*N*N) and also SC of an additional O(N*M)
@@mohaimenchowdhury its giving tle on LC though.
Great observation bro
Learnt how to check for subsequence using two pointers.
Understood.
understood , thank you striver
Now , i feel so much confidance . i applied same exact code and i came just to see your stretegy. 😃
that's the best feeling in the world
solved this without watching because of Striver !!!
Thank you
Understood!
Understood ❤
We love you striver!!!
in c++ your comp function should be static since sort() is static .(if code is in class)
#understood....thanku striver
Understood:)
Thank you , understood.
you are amazing sir
i am getting tle with recursive dp on last test case .. can it be done with recursive dp?
keeping the idea simple and building up the solution is a rare art only our Savior Striver possesses . Thankyou for amazing solution Striver
Understood, sir. Thank you very much.
understood!
another complex way of solving it using recursion(c++)
#include
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&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 longestStrChain(vector &arr)
{
sort(arr.begin(),arr.end(),compare);
int n = arr.size();
return solve(arr,0,n,-1);
}
cant find in which video you explained the LIS code you typed in the begining of this video. Please help.
just go tthis playlist, and you will find in dp 42/43
@@takeUforward oh ok. Thanks 🙏
Understood Sir, Thank you very much
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!!
Anything inside nested loops (Eg. "for loop till n" and "for loop of prev" and the "checkPossible" function) are multiplied and if some block of code is outside nested loops, it's added to the complexity.
Hence here, (first loop runs till N) * (Second loop of previous runs till N) * (checkPossible function runs till max length of the string) = (N^2) * len
If our checkPossible function was outside these loops then it would have been added and not multiplied.
Therefore, Multiplication is done from the outermost loop of any nested block till the interiormost loop.
@@aniket7512 Ohh!! What about when we have recursion or some other operations? How do we know the time complexity? Or is it just based on the loops?
And thanks a ton for answeringg!! Much appreciated!
@@tasneemayham974 Recursion case complexity is calculated by visualising the recursion tree with the depth and the branches it goes. Try some examples on ur own with the previous videos of striver's.
If not let me know if any doubt u have.
@@aniket7512 Ahh yes!! Actually I watched his whole series and that's the only way I calculate the TC. I just thought there was another rule for that! So, thanks for clearing that up!! You were really helpful!! BIG THANKS BRO!
is it possible to solve this by tabulation approach, or memorization approach
In checkpossible function, in not match case, shouldnt it be second++ as, s2 being the larger string
Great Explanation
understood ,able to solve by my own
Understood, thanks!
What does he mean when he says "shuttle changes"?
subtle changes i believe
@@vamsikrishnar8550 Yeah right. Thanks!
How does the comparison
s1[first] == s2[second] work in case we overshoot second to be greater than s2.size ?
Wouldn’t s2[second] in that case would give a segmentation fault ?
need to one more condition in if( second < s2.size() && s1[first] == s2[second] )
Understood 🎉
understood
thanks
understood!!
Understood!!!Thank you
Understood!
what is the time complexity of recursion code of this question? recursion code accept on gfg.
Understood.
checkPossible method should return false when s1 = "aa" and s2 = "aa". But currently it returns true
in c++ if getting error in comparator function make it :- static bool comp
But why?
Understood. Amazing !
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.
what will be the time complexity of this ?
sorting actually reduce the number of comparisons of 2 strings pair as we wont be iterating for all string only those who are less than it, or can be done with the help of map as well, if you done word ladder, similar kind of approach
"understood" ❤
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
Correct if you dont declare the bool functions static it gives TLE on leetcode
Leetcode has very tight constraints.
Can you explain how adding that else condition takes care of the case where s1=abcd and s2=abc?
// t.c - O(nlogn) + O(n^2m);
class Solution {
bool checkPossible(string &s1, string &s2) {
// ith string has to be one greater than the prev
if(s1.size() != s2.size() +1) {
return false;
}
int first = 0, second = 0;
while(first < s1.size() && second < s2.size()) {
if(s1[first] == s2[second]) {
first++;
second++;
}
else{
first++;
}
}
if(first == s1.size() && second == s2.size()) return true;
else if(second == s2.size()) return true;
return false;
}
static bool comp(string &s1, string &s2) {
return s1.size() < s2.size();
}
public:
int longestStrChain(vector& arr) {
int n = arr.size();
// sort acc. to the length of string
sort(arr.begin(), arr.end(), comp);
for(int i=0;i
class Solution {
public:
static bool comp(string s1, string s2){
return s1.size()
@@Shubham-or6cs ["xbc","pcxbcf","xb","cxbc","pcxbc"] on this TC ?
Hey it would be a great help if you upload the notes and java code on your website, for these programs.
notes are there if you see in description and java code can be found in comments down below
Understood!!!!!
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
hey striver! I can't find the notes for this problem on takeUforward website. is it still not updated? do we have to wait?
Yes end of june is expected date
@@takeUforward we are waiting
@@takeUforward We are still waiting for the notes to be uploaded.
Sir please also make a video on scramble string
Getting Time Limit Exceeded on leetcode, any suggestions for optimization ?
in checkPossible function , pass the two strings as reference like &str1 ,&str2
if(words[i].size() == words[j].size() +1 ) .....use this condition before compare condition
@@ShubhamKumar-ur1vm now its working lol but why???
understood ❤
Can I print subsequence only using iteration not using power set in iteration of possible can you make a video on that
use static bool cmp on leetcode else it wont work and also declare string with const string in the cmp function
sort(arr.begin(),arr.end(),[](string a,string b){
return a.size()
@@getthejobdone5419 It looks more complex than just adding static
why we write s1.size() != s2.size() +1)
I am getting a tle for the same code on leetcode, can anyone suggest how to resolve it .
Try sorting the given string based on len and break the second loop if the diff of lengths is >1
for index in range(len(words) :
for prevIndex in range(index-1,-1,-1) :
lenCondition>1: break
Understood 😇
Understood!!!!
Undertoor, thanks
understood sir🙏❤
why take and notTake approach is not working in this ?
Understood
Comparison function if s1=cbd and s2=bc it will not work ?? Can anyone explain
we can't change the order of b and c. check on leetcode its clearly mentioned order have to be same. only 1 character can be inserted anywhere in the string for new member of chain
Understood
But can anyone let me know how to figure out that this question has to be solved using LIS pattern
Has anyone found striver's comparator 15:11 video?
understood'
Understood !!!!!!!!!!!!!!!!!
Can we do this using the binary search logic as well??
If yes , can anyone put the code
understand
Understood💪💪💪
understood!
Understood ❣️
tooooooooooooo goooooooooooood
understood❤❤
understood dude:)
Understood!
DP Revision:
Had to watch whole of the video to get the logic ;-;
Nov'20, 2023 04:42 pm
It can be done in N*L right ?
How?
@@thinkingmad1685 I was wrong ,it will be NL²
understood!!!!
i thought of exact same approach but it gives tle on leetcode:(
Understood Sir!
understood!!
"understood"
good raj vikram aditya
Understood!!!
genius
understood
Understood Sir :)
Java Code for this?
Check out my solution,
leetcode.com/problems/longest-string-chain/discuss/2223228/Java-Simple-solution
Understood Sir
Anyone getting static error use this:
static bool sor(string &a, string &b) {
return a.size() < b.size();
}
not me
public static boolean compare(String s1, String s2){
int first = 0;
int second = 0;
int diff = 0;
while (first < s1.length()){
if(second < s2.length() && s1.charAt(first) == s2.charAt(second)){
first++;
second++;
}else{
diff++;
first++;
}
}
if(first == s1.length() && second == s2.length() && diff == 1){
return true;
}else {
return false;
}
}
// //Check Predecessor by checking LCS and then use LIS logic.
// public static int lcs(String a, String b, int i, int j, int[][] dp){
// if(i
#include
using namespace std;
bool comp(string &s1, string &s2)
{
return s1.size() < s2.size();
}
bool checkstr(string &s1, string &s2)
{
if(s1.size()!=s2.size()+1) return false;
int first=0, second=0;
while(first < s1.size() && second < s2.size())
{
if(second
Same problem
the while loop should run s1.size() times
so while(first < s1.size())
Make comp func static
Make comp static and run the while loop for(first
Here is my memoization code. which gave me TLE.
struct compare {
inline bool operator()(const std::string& first,
const std::string& second) const
{
return first.size() < second.size();
}
};
bool check(string s , string t){
int n = s.length() , m = t.length() , count = 0 , i = 0 , j = 0;
if(m != (n + 1)) return false;
while(i < n){
if(s[i] == t[j]){
i++ , j++;
}
else{
count++;
j++;
}
if(count >= 2) return false;
}
return true;
}
int solve(int i , int prev , vector < string > &v , vector < vector < int > > &dp){
int n = v.size();
if(i == n) return 0;
if(dp[i][prev + 1] != -1) return dp[i][prev + 1];
int len = solve(i + 1, prev , v, dp); // notTake
if(prev == -1 || check(v[prev] , v[i])){
int take = 1 + solve(i + 1 , i , v , dp);
len = max(len , take);
}
return dp[i][prev + 1] = len;
}
int longestStrChain(vector& words) {
int n = words.size();
compare c;
sort(words.begin() , words.end() , c);
vector < vector < int > > dp(n , vector < int > (n + 1 , -1));
return solve(0 , -1 , words , dp);
}
---------------------------------------------------------Tabulation---------------------------------------------
int longestStrChain(vector& arr) {
int n = arr.size() , maxLen = 1;
compare c;
sort(arr.begin() , arr.end() , c);
vector < int > dp(n , 1);
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(check(arr[j] , arr[i])){
dp[i] = max(dp[i] , dp[j] + 1);
maxLen = max(maxLen , dp[i]);
}
}
}
return maxLen;
}