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; }
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
@@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)
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
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.
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
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
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!
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
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 ?
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
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?
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.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
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
What an amazing thought process. I haven't seen anywhere yet.
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 :)
solved this without watching because of Striver !!!
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);
}
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
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
Learnt how to check for subsequence using two pointers.
understood , thank you striver
As always "understood" ❤️
Understood! Thank you veeeeeery much as always!!
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
in c++ your comp function should be static since sort() is static .(if code is in class)
keeping the idea simple and building up the solution is a rare art only our Savior Striver possesses . Thankyou for amazing solution Striver
We love you striver!!!
Thank you
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 ?
#understood....thanku striver
Understood, sir. Thank you very much.
Understood Sir, Thank you very much
checkPossible method should return false when s1 = "aa" and s2 = "aa". But currently it returns true
Understood.
you are amazing sir
Understood ❤
Thank you , understood.
i am getting tle with recursive dp on last test case .. can it be done with recursive dp?
understood ,able to solve by my own
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!
Understood:)
Great Explanation
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 🎉
In checkpossible function, in not match case, shouldnt it be second++ as, s2 being the larger string
understood!
is it possible to solve this by tabulation approach, or memorization approach
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
DP Revision:
Had to watch whole of the video to get the logic ;-;
Nov'20, 2023 04:42 pm
Sir please also make a video on scramble string
Understood, thanks!
Understood. Amazing !
Understood!!!Thank you
thanks
understood
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.
what is the time complexity of recursion code of this question? recursion code accept on gfg.
Understood!
"understood" ❤
understood!!
Understood!!!!!
What does he mean when he says "shuttle changes"?
subtle changes i believe
@@vamsikrishnar8550 Yeah right. Thanks!
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 !!!!!!!!!!!!!!!!!
Undertoor, thanks
Understood.
Understood
good raj vikram aditya
Can I print subsequence only using iteration not using power set in iteration of possible can you make a video on that
Understood!!!!
"understood"
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
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
in c++ if getting error in comparator function make it :- static bool comp
But why?
Understood Sir!
Understood!
tooooooooooooo goooooooooooood
Understood 😇
why take and notTake approach is not working in this ?
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 ❤
understand
understood dude:)
Understood ❣️
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
Understood Sir
understood sir🙏❤
Understood!!!
why we write s1.size() != s2.size() +1)
understood'
It can be done in N*L right ?
How?
@@thinkingmad1685 I was wrong ,it will be NL²
understood!!!!
genius
Understood💪💪💪
understood!!
Understood Sir :)
Understood
Can we do this using the binary search logic as well??
If yes , can anyone put the code
Has anyone found striver's comparator 15:11 video?
understood
As always "understood"
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;
}
Understood
But can anyone let me know how to figure out that this question has to be solved using LIS pattern
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
Anyone getting static error use this:
static bool sor(string &a, string &b) {
return a.size() < b.size();
}
not me
understood❤❤