DP 45. Longest String Chain | Longest Increasing Subsequence | LIS
Вставка
- Опубліковано 7 кві 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
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/takeUforward
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.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
What an amazing thought process. I haven't seen anywhere yet.
Understood! Thank you veeeeeery much as always!!
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?
UNDERSTOOD.........Thank You So Much for this_wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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.
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 :)
We love you striver!!!
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
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
Understood Sir, Thank you very much
Understood, sir. Thank you very much.
As always "understood" ❤️
Thank you , understood.
Understood. Amazing !
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
Understood ❤
Great Explanation
understood ,able to solve by my own
Understood!
Understood, thanks!
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 ?
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);
}
i am getting tle with recursive dp on last test case .. can it be done with recursive dp?
understood!!
Sir please also make a video on scramble string
thanks
Understood!!!!!
Understood.
understood
In checkpossible function, in not match case, shouldnt it be second++ as, s2 being the larger string
Can I print subsequence only using iteration not using power set in iteration of possible can you make a video on that
solved this without watching because of Striver !!!
Understood:)
Understood !!!!!!!!!!!!!!!!!
Understood
in c++ your comp function should be static since sort() is static .(if code is in class)
understood sir🙏❤
understood'
Undertoor, thanks
what is the time complexity of recursion code of this question? recursion code accept on gfg.
Understood!!!
understand
"understood" ❤
understood!
understood ❤
understood❤❤
understood dude:)
Understood ❣️
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 🙏
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.
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] )
in c++ if getting error in comparator function make it :- static bool comp
Understood 😇
DP Revision:
Had to watch whole of the video to get the logic ;-;
Nov'20, 2023 04:42 pm
Understood 🎉
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💪💪💪
Understood Sir!
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 ?
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!
What does he mean when he says "shuttle changes"?
subtle changes i believe
@@vamsikrishnar8550 Yeah right. Thanks!
Can we do this using the binary search logic as well??
If yes , can anyone put the code
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
tooooooooooooo goooooooooooood
#understood
why take and notTake approach is not working in this ?
As always "understood"
Understood Sir
genius
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 :-)
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???
why we write s1.size() != s2.size() +1)
Understood Sir :)
It can be done in N*L right ?
How?
@@thinkingmad1685 I was wrong ,it will be NL²
#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
Understood
But can anyone let me know how to figure out that this question has to be solved using LIS pattern
6:30
good raj vikram aditya
US
US
i thought of exact same approach but it gives tle on leetcode:(
Java Code for this?
Check out my solution,
leetcode.com/problems/longest-string-chain/discuss/2223228/Java-Simple-solution
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
US❤
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;
}
"us"
undeerstooooooooooodddddddddddddddddddddddd
us
"Understood"
khudse kiya
😃
ud
it gave a tle on leetcode but passed on code studio
class Solution {
public:
static bool comp(string s1, string s2){
return s1.size()
@@Shubham-or6cs check the if condition inside the while loop in checkPossible function. It should be
" if( second
Bhaiya notes updated nhi hai 🥲
Working C++ Solution
class Solution {
public:
bool checkPossible(string &s1 , string &s2)
{
if (s1.size() != s2.size() + 1) {
return false;
}
else{
int first=0,second=0;
while(first < s1.size())
{
if(s1[first]==s2[second]){
first++;second++;
}
else {
first++;
}
}
if (first == s1.size() && second == s2.size()) {
return true;
} else {
return false;
}
}
}
static bool cmp(string &s1,string &s2)
{
return s1.size() < s2.size();
}
int longestStrChain(vector& arr) {
int n=arr.size();
vector dp(n,1);
int maxi= 1;
sort(arr.begin(), arr.end() , cmp);
for(int i=1;i
yoyo]
Us
us....
Bhaiya can u reduce the size of your image into a small box or circle
Ipad ittu sa hi h, if i elongate, the reso goes off!