Longest String Chain | Same as LIS | FULL INTUITION | DP Concepts & Qns - 14 | Leetcode-1048

Hi Everyone, this is the 14th video of our Concepts Playlist "DP Concepts & Qns".
Today we will solve our 1-D DP problem which is a variant of the Longest Increasing Subsequence "Longest String Chain" (Leetcode-1048).
We have already studied LIS using Recursion+Memo and Bottom Up in Video-11 and 12

If you have been following my "DP Concepts & Qns" playlist , then these will become very easy.
Make sure to watch from the beginning of this playlist to master DP in the easiest way possible.

My aim is to make DP easy and make everyone believe that once you get clarity , you can solve even DP Qns Easily.
It will no longer be a Nightmare topic for anyone. All I need is your attention for some time and CONSISTENCY.

"If someone can, we can too"

Problem Name : Longest String Chain
Company Tags : GOOGLE

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[aman_v]

9:35 bottom up approach se ho gaya guruji

[gocrazy]

Paused the video and coded the solution myself without looking at your single line of code. Solved with memo and got accepted.

[honey]

today I have done your 543 videos in just 1 month and learned's lot of new skill that I was strictly lacking .. thanks you sir..

[dhairyachauhan]

I think the trick to know if a question is of lis is
Check the following:
1) Most of the time question starts with Longest chain, Longest
2) ask yourself can there be a subsequence( j ) which upon doing operation x will end at the current value(i).

This always works for me hope it helps others too.... :)

[ManishGupta-lzho]

guys lets share this channel in every group of coding,

[aadil]

Yaar, mene pehle waala question kiya hua tha. Lekin solve ni hua, muje laga ke dp ka he, phir bhi me pata ni HashMap ke saath kya naatak kar raha tha, us Hash waale solution me mene 2 ghante kharab kardiye phir mene give up hi de diya aur yaha aagaya dekhne, ek dam se samaj me aa gaya. Thank you bhai!!

[rahultoo]

greatness and humbleness is the quality of god 🙏🙏

[AlishaKhan-wwio]

I feel blessed to have found this amazing channel. I paused the video in the middle and was able to code it up using lis code. Thanks a lot ❤❤❤

[Lakshya-fl]

Learnt a lot from this video!
Thanks a ton bhaiya ! :-)

[wearevacationuncoverers]

One one stop solution. Thank you MIK the legend

[mewaconite]

I think it would be easier to write LIS function if we do prevIndex + 1.... while storing in dp

```cpp
int lis(vector<string> &arr, int prevIndex, int currIndex){
// 1. base case -> reached end of words array
if (currIndex == n){
return 0;
}

// check in memo
if (dp[currIndex][prevIndex+1] != -1) {
return dp[currIndex][prevIndex+1];
}

// 2. pick or unpick
int pick = 0;


if (prevIndex == -1 || isSubsequence(arr[prevIndex], arr[currIndex])){
pick = 1 + lis(arr, currIndex, currIndex + 1);
}
int unpick = lis(arr, prevIndex, currIndex +1);

return dp[currIndex][prevIndex+1] = max(pick, unpick);
}
```

Thank you for another amazing video... can't wait for 10k :D

[HealthyOm]

love u bhaiaua we want such more conceptual vedios

[FYJGauravShelke]

class Solution {
public:
static bool comp(string s1, string s2)
{
return s1.size()<s2.size();
}
int words)
{
int ans=INT_MIN;
int n=words.size();

sort(words.begin(), words.end(), comp);
for(int i=0;i<n;i++)
{
int count=1;
string first=words[i];
for(int j=0;j<n;j++)
{
// bool ispossible=false;
if(j==i)
{
continue;
}

int curr_size=first.size();

{
int ind=0;
int count_extras=0;
// cout<<words[j]<<endl;

for(int k=0;k<words[j].size();k++)
{
if(count_extras>1)
{
break;
}
else if(words[j][k]==first[ind])
{
ind++;
}
else
{
count_extras++;
}
}
if(ind==(first.size()))
{
// cout<<words[j]<<endl;
count++;
first=words[j];
}

}


}
ans=max(ans, count);
cout<<endl;
}
return ans;
}
};

this code is giving 74/85 test case passed
what is wrong in this code

for below testcase
["a", "ab", "ac", "bd", "abc", "abd", "abdd"]

output --> 3
expected ---> 4

why 4 as there are only three
a-->ab-->abc that's all
how ans is 4?

please @codewithstorymik explain me

[jagratgupta]

very nice explanation sir.I understood LIS also (great intuition and explanation)...

[AbhijeetMuneshwar]

Quote of the day:

When you don't feel like studying, always remember, "Someone is working harder than you to get that job"

Thank you MIK sir for inspiring me 🙏🙇

[floatingpoint]

great explanation. one suggestion: please add the complete tree diagram in the notes pdf if it increases the video length thanks a lot

[FanIQQuiz]

I will repeat, this guy is a living LEGEND.
I will again ask the same Qn until you answer me - "Why don't you ever ask us to Subscribe or follow your insta etc ? " You have never ever done that in any video. Sir please tell 😅
"Janta jawab chahti hai😅

[dayashankarlakhotia]

class solution {
public int longest Str Chain (string []words){
Array. sort (word, (a, b)-->a.length ()-b.length());
Hash map <string, interger>mpp=new Hash map >>();
int res=0;
for(string word:words){
mpp.put (word, 1);
for(int i=0;i<word.length;i++){
string s=word.sub string (0, i)+word. sub string (i+1);
if(mpp.contain key (s)){
mpp.put (word, MATH.MAX (mpp.get(word), mpp.get (s)+1));
}
res=MATH.MAX (res, mpp.get (word));
}
}
return res;
}
};
Tc=nlognnm
sc=(n)
n=words. length
m=sub string. length
for sorting logn+traversal of words=n+sub string find m+ traversal to make sub string n;

[sujitkumarsangramsingh]

Bhaiya please continue DP concept and q&n series...please

[HemantYadav-ypzi]

Hello sir, Please make a video on count valid paths in a tree which is the last question of leetcode contest 364