30 Longest repeating subsequence
Вставка
- Опубліковано 4 лют 2020
- Longest Repeating Subsequence
Given a string, print the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., any i’th character in the two subsequences shouldn’t have the same index in the original string.
Example:
Input: str = "aab"
Output: "a"
The two subsequence are 'a'(first) and 'a'
(second). Note that 'b' cannot be considered
as part of subsequence as it would be at same
index in both.
PROBLEM STATEMENT LINK:www.geeksforgeeks.org/longest...
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
This solution is also updated on GFG with 2nd part to print Longest repeating sub sequence
u are actually helping GFG to updating its article.
Bro ,do you have any plan to publish the series on "graph".
@OttoLyle @Mauricio Weston.. u both seems to be of same mother but diff fathers
no
@@Prince-fz6yo 😂😂😂😂
@@maharajak6578 bhai this weston dude's comment got deleted ig, what did he say tho?
@@arafatkhan5489 haha i also didnt get
Whoever has confusion in the following inputs :
AABABCD
AXXXY. etc.
Here is the explanation:
Read this: Given a string, print the longest repeating subsequence such that the two subsequences don’t have same string character at same position
The same Position is the twist here: A X X X Y ==> You can take X X [index0 and index1] and XX [index 1 and index2]
X of index1 is used in both but its position in both substrings is different. In the first subsequence, it comes at 1st index whereas in
the second subsequence comes at the 0th index.
Case :- AABCABB
ANS :- 5
This question is little bit confusing read it twice if anyone is confused.
@@hemantmangwani1006 The answer should be 4 for the string "AABCABB" not 5
@@DeepakKumar-yl3ok yes
RAJ Kumar why is it not 3
@@bhaswatraj9433 No answer will be four you can cross check it by applying on algorithm
Whole Series is just awesome , Great explanation and thought process
literally the logic of this problem comes to my mind automatically after watching your DP playlist.
please make more videos on weighted graphs ,shortest paths ,prim ,krushkal ,,from codeforces
no words to express your teaching...🤔🤩..... i was thinking about to solve it by this way that take both string and find lcs but then i defeated because they are same.... because of leaving idea in half way i was not able to solve that by own.... then you enlightened... you're great.....
I relinquished the idea of taking the second string similar to first one due to the same reason.
Simply Genius!!...........Please bring graph series too
29 of 50 (58%) done! Very nicely done!
It doesn't mean that you achieved something here, hold back and practice
@@pr1493 if u cant support, atleast don't be toxic
@@prateekchauhan5376 Just tried to push that guy to practice more without getting complacent, Don't know what ails you here lol 😂
@@pr1493 jada cool mat ban bhai... tune kya kiya you also know it.
@@deepakpandey3485 We can talk when you have a job
untouchables ..dank bhai😂😂
Thank you bro, you have great teaching and explaining skills
Can you make a video on Longest Increasing subsequence.
Are simple h ye gfg p diya huaa h..
Arr1 -input arr
Arr2 - arr1 ko sort karo.
LCS(Arr1, Arr2)-> ans..
That's it bas itna sa hi h! 😎
@@anandabhinav If there will be repitition in array it will give wrong ans
@@maximus6448 bro binary search wala approach use karrlenge phirr.
@@yashbhanushali8456 remove duplicates from the sorted array.
@@anandabhinav remove duplicated from sorted array
Amazingly explained bro. Itne easy-going flow me samjhaya hai ki Binge watching chal rhi hai :D
Awesome content I am waiting for more such videos... your explanation is good.
Thank you very much. You are a genius.
Just checking upper or lower triangle is enough right, like
i=1 to n, j=i+1 to n - return dp[n-1][n] (upper) or
i=1 to n, j=1 to i-1 - return dp[n][n-1] (lower) .......
(solved in GFG - 100%)
Anyhow, u r making our lives easy, we owe you a lot
LOL - lots of love ❤ also gratitude 🙏
what does the cell value of dp matrix represent here ??
It represents the longest repeating subsequence that can be formed using the first x no. of elements of the given string , where x is the column no. of that cell
Oh !! my bad, both strings are equal😂😂 @5:50 ..
..
..
By the way your DP tutorial is best sir❤❤..
haha
5:46 . hahahha !! of course they all will match since they are same. jokes apart this had been one of the best learning for DP. Glad YT showed in search when I typed dynamic programming. Thanks a ton !!
Great Explanation sir ! Can We solve this problem using auxiliary lps array which we make in KMP algo and than we can find max imum element in that lps array ??Will this approach work for this problem ??
Sir plz complete this playlist of dynamic programming
It's humble request sir plz
Upload the video sir as soon as possible
Those who don't get why i!=j,
if s1 = "ABBC", s2 = "ABBC" then answer should be 1 which is "B"
here when we create matrix :
A B B C
0 1 2 3 4
0 0 0 0 0 0
A 1 0 0 0 0 0
B 2 0 0 0 1 0
B 3 0 0 1 0 0
C 4 0 0 1 1 1
so the answer will be 1
as s1 = "ABBC", s2 = "ABBC"
in first iteration i = 1, when we at i index of B(s1), then we will not count ith index of B(s2), but we will count the ith+1 index, for i = 1 iteration and same is the case with jth iteration of B...
One doubt here:
why the answer is 1 which is "B", in the question (on gfg), an example is given like this:
A = "xax" and B="xax" then first character "x" should have different indexes, the other can have same,
answer of string s = "xxax" is 3 as "xax" and "xax" are the longest repeating subsequence, here "x" starting of both strings is having different indexes
public class longestRepeatingSubsequence {
public static void main(String[] args) {
String s1 = "axbyczapbqcr"; // "abc" is repeating here, so ans length is 3.
String s2 = s1; // Create a copy of the input string s1 for comparison
int n = s1.length(); // Length of string s1
int m = s2.length(); // Length of string s2 (copy of s1)
// Create a 2D DP (Dynamic Programming) table with dimensions (n+1) x (m+1)
int[][] dp = new int[n + 1][m + 1];
// Initialize the DP table with zeros
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0; // Base case: If either string is empty, LCS is 0.
}
}
// Fill in the DP table using a top-down approach
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
if (i != j && s1.charAt(i - 1) == s2.charAt(j - 1)) {
// If the current characters match and the indices are not the same
// (ensuring they are not the same character at the same position),
// add 1 to the previous LCS length.
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// If the current characters do not match or if the indices are the same,
// take the maximum of the LCS when one character from either string is
// excluded.
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// The value at dp[n][m] contains the length of the Longest Repeating
// Subsequence (LRS).
int result = dp[n][m];
// Print the length of the LRS.
System.out.println("Length of Longest Repeating Subsequence: " + result);
}
}
We can also do
for(int i=1; i
why ?
@@kshitiz5621 Because you can't use the same character in the repeating sequence.
best explanation of the Longest repeating subsequence
This was a very good question solved in an easiest manner ever!
lovely explanation!! great work man ♥♥
please also make videos on graph topics like BFS, DFS and Shortest path.
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@@TheAdityaVerma next video kab aayega bhaiya??
@@TheAdityaVerma its been more than a year, still no videos on graphs 😔😭
@@TheAdityaVerma its been than 2 year, still no videos on graphs.
@@TheAdityaVerma We Want Graph Series.
Bro i am watching your videos from 4 days and subscribers have increased by atleast 500 , 😁😁 placement season is approaching , do u want to give some tips regarding coding tests of companies?
thank you aditya bhaiya because of you i am able to solve the different kind of question
Amazing Explanation🙌🙌
If i want to write above recursive code every time happens tle because gfg always ask O(N^2) time complexity then what should i do?
I have a better sol. : make a hashmap to map characters to their count. Then ans = ans + count/2 ... here we are dividing count of each character by 2 to get the max length repeating substring . This will take O(N) time as there are only 2 iterations and also no 2d is required .
Bro the code using hashmap cannot gurantee about the subsequence. Correct me if i am wrong
it wont work try for this : ABADDBE
After watching your playlist
I think we should use
- Bottom up approach when we have to print numbers, strings etc.
- Top down approach when we have to count the numbers, characters etc. according to question.
Well, thanks me later if you agree......
Ya you are right.
its actually interesting, that you should use tabulation where you have to perform operations on the created table itself, ie in such cases tabulation is necessary because it is just a mid part of a larger problem.
Amazing Explanation🙌🙌
It's just like a magic happened in every video..👏👏🔥🔥
Bhai u made dynamic programming like sweet
Bro we got AABBDD on taking all these conditions in mind.. shouldn't we do half of it to get final answer??
Awesome..No words....
Thank you so much 😀
This technique won't work for every test case.
For string = 'ABEBACDD', The repeating subsequence is 'AD' only. As the order of subsequence matters, 'ABD' and 'BAD' can't be considered as equal. So the logic to compare only mismatch indexes will fail as it'll give output as 3 but the correct answer should be 2.
One solution would be to remove all the repeating characters from the string s1 and store it in a separate variable s2, then if we take LCS of s1 and s2 that would give the answer.
For string = 'ABEBACDD', s1='ABECD' (by removing repeating chars) s2='BAD' (removed chars in same order). LCS = 'AD' so length is 2.
Let me know if this is incorrect. Don't want to mislead anyone :)
I tried this string with the approach explained in the video and got answer 2. Here's the top down matrix for this
A B E B A C D D
[0, 0, 0, 0, 0, 0, 0, 0, 0]
A [0, 0, 0, 0, 0, 1, 1, 1, 1]
B [0, 0, 0, 0, 1, 1, 1, 1, 1]
E [0, 0, 0, 0, 1, 1, 1, 1, 1]
B [0, 0, 1, 1, 1, 1, 1, 1, 1]
A [0, 1, 1, 1, 1, 1, 1, 1, 1]
C [0, 1, 1, 1, 1, 1, 1, 1, 1]
D [0, 1, 1, 1, 1, 1, 1, 1, 2]
D [0, 1, 1, 1, 1, 1, 1, 2, 2]
sorry for the uneven spaces in top header row. I couldn't get the alignment right any other way
Another suggestion, you can change the inequality from (i != j) to (i < j). In effect it means that the ith character in 1st string can match a character at j in 2nd string only if its ahead of index (i). It gives a more understandable matrix
A B E B A C D D
[0, 0, 0, 0, 0, 0, 0, 0, 0]
A [0, 0, 0, 0, 0, 1, 1, 1, 1]
B [0, 0, 0, 0, 1, 1, 1, 1, 1]
E [0, 0, 0, 0, 1, 1, 1, 1, 1]
B [0, 0, 0, 0, 1, 1, 1, 1, 1]
A [0, 0, 0, 0, 1, 1, 1, 1, 1]
C [0, 0, 0, 0, 1, 1, 1, 1, 1]
D [0, 0, 0, 0, 1, 1, 1, 1, 2]
D [0, 0, 0, 0, 1, 1, 1, 1, 2]
Hello@@vineetchaurasia6600 ,
I found that this itself is correct, no need to change i < j.
Reason being the other condition we are looking for which eliminates ABD and BAD in answers, is covered in LCD itself and we are getting '2' in second last place of last row because X[6] is compared to Y[7] which would never occurs as X == Y, X is string1 and Y is string 2.
And,
Thank You for the matrix, it really helped for me too.
great explain thanks you
solved it in an iterative way. DP is not needed for this. Here is the golang code:
func sequencePattenMatching(str1,str2 string) bool {
// Characters in str1 should match a subsequence in str2
i := 0
j := 0
str1Byte := []byte(str1)
str2Byte := []byte(str2)
for i < len(str1) && j < len(str2) {
// Check if str1[i] is present in str2
for j < len(str2) && str1Byte[i] != str2Byte[j] {
j++
}
if j == len(str2) {
return false
}
// Found
// Increment i
i++
}
return true
}
Input: str = "axxxy"
Output: 2
Why above has output as 2(XX).
index 2,3 and index 3,4 ... one X is overlapping
what should be output of axxxy? If anyone can explain?
Nice explanation
so if we will remove the unique characters from the string that should do the work?
Nope,as in subsequence order also matters
@@AmitSingh-cs2hb I think it will work fine if we want to count the size because in counting size the order does not matters
@@pranjalbansal8459 only removing unique characters wont work becz we have to print the lenght of characters which are duplicate and they should manitain there order also for example "AABEBFCDDF" the answer will be still ABD not ABFD .
Hi Aditya,
Big thank you,
Can you please make a playlist of the graph ???
Hey, Aditya( I am again going to bother you lol)
Are you thinking to upload videos on DP on grids and LIS anytime soon?
Thanks in Advance 😀
Have you found any series like this for dp on grids, lis Or even understandable in yt pls suggest me 😔
@@thinkingmad1685 Watch Striver's DP playlist for these topics. He explained all of them very well..
nice explanation
Thanks!
We can also do these question using frequency mapping
well greedy will also work well , think this way the maximum times a character occurs will be length of lrs . cuz a single character too a subsequence..,but if length >1 then we need to go by dp......
update: i misunderstood problem:((((
@@divineforever8691 LOLOLOLOLOLOLOLOLOL
@Aditya Verma
For AABBEBCDD its not working
in this B comes thrice and giving us wrong output
He did a mistake in explain problem statement.
You can take same character of string in longest repeating subsequence. See if put two same string side by side then you will observe that 'B" at thired index can be used twice.
Zeroth index 'A' match with first index of second. Second index 'B' match with thired index of 'B'.
Thired index 'B' match with fifth index and lastly seventh index 'D' match with eight index.
You can notice in orignal string that thired index 'B' is considered twice.
6: 36 it's wrong if you say those things as a teacher or as any kind of literate person. It shows that even in this modern era, You just subconsciously cannot get rid of that mentality.
Will it work for input such as AABBDDABD where the output should be 3
Mine giving o/p as 4
yes bcoz the ans is ABDD first lcs at index 0 2 4 5 and second lcs : 1 3 5 8
the twist here is Given a string, print the longest repeating subsequence such that the two subsequences don’t have same string character at same position
@@satyalakshmiyeleti1149 where will i find the 2nd ABDD there is only one ABDD in the string
@@kanhav03 at index 1 3 5 8 : A B D D respectively
Can someone explain LRS for :
aabbccdefclcicd
As per my calculations it should be abccd
As this subsequence can be extracted 2 times, but using the dp approach I am getting "abcccc" as the result, did I misunderstand LRS and the answer should be abccc , or something is missing in this dp approach?
The correct answer is abcccc as it's length is more than abccd. Now why abcccc is the answer is because you have 5 c's in the original string and 1 subsequence took 1,2,3,4th occurrence and the other took 2,3,4,5th occurrence so each occurrence of c is different for both the strings. I hope you understood.
@@ashishchawla2718 ohh so c1,c2 c2,c3 c3,c4 c4,c5 making 4 pairs and its possible bcz the only condition that we following is i!=j and following the ordering of subsequence, I think i got it
Thanks
If we take an example as "ABBCA"
the longest repeating subseqence has length 1
But here both A and B are repeating means has different indexes?
I am little confused can somebody help me?
AB will not be a subsequence here since the order is not maintained
"Untouchables hai, nahi hai...". Lol
bhai chota sa question itna complicate kiya aapne maza aa gya
use unordered map input the string in it with thier count.....count the number of odd counts(values) present in map and minus it with the length of string...and output will be result diveded by two
This won't work since the counting will not always mean that the sequence of characters is same. For eg. "ADDA" .Here "AD" and "DA" will be considered as different subsequences and the correct answer will be 1,not 2 .
Can't we use directly UNORDERED MAP ??? We will ignore those elements which occurred only once. PLEASE CLARIFY MY DOUBT
We can do that, definitely
I think I have a better approach not sure if it always true:
Find number of occurrences that are greater than 1.
And divide each of them with the min repeating count and add them up. That is your longest repeating subsequence,
Eg - ADBABDADA
A - 4
B - 2
D - 3
Since B has min number of occurrence, divide each by 2.
So, we get => 4/2 = 2, 2/2 = 1, 3/2 = 1
So longest repeating subsequence = 2 + 1 + 1 = 4.
I tries it and it logically fits in as large string as size of 10.
Not sure though.
but what about order try ABBAC
MZA AA GYA DP SEIES SIR
cant we do this by using simple hashing ??.if any of the index is greater than 1 then we add 1 in our answer ? correct me if im wrong
take string AABDDB. Your logic won't work here
@Aditya Verma where are you? Why you are nit uploading videos?
bhai yeh question toh greedy se bhi toh possible hai... we will just count number of character in the hashmap and which is greater then 1 we will count it and finally return the count. isn't it? Tell me if iam doing wrong somewhere ?
by your logic "caac" will give ans 2, but the answer should be 1. Whenever subsequences are involved, we shoukd consider all options, but greedy won't do that.
gazab ka explanation .......
Thank you bhaiya
Hey, we should compare the given string itself, right? No need to reverse the given string and compare.
What if the series is ABCDDCBA the longest repeating subsequence is just DD not ABCD
So will this code run?
won't LRS be "D" and not "DD"?
@@RajatGupta-lq3cb yes, only "D"
Need a playlist on GRAPH !!
You should try Striver's Graph series. It really helped me in clearing my concepts.
Nice one , but we can extract the repeating character from the LCS by using hash map if I am not wrong
Same thought
HashMap do not preserve the order
@@vineetjain7518 we can have a list of indexes in the value part of the map?
@@sushmitagoswami2033 it will throw an exception as from list an element can be removed add at any specific position therefore compile time error
Bhaiya lol to ur teaching 🥰 ......who else wants to say the same lines to bhai with me
Awesome yrr!!!
Thanks brother, Do subscribe and share, that keeps me motivated to do more !!
faad diya bro faad diya.....!!
Hn bhai.😅
thanks buddy :) , @5:50 leaving 'e' while finding LCS of same string was funny though :D
last me jo output aayega usko 2 se divide bhi karna padega na ?
yess
@@kshitijgaur9635 job lag gayi ab jarurat nahi😂😂
@@PeaceLoveAman Congratulations bro!!!!
class Solution {
public:
void solve(int index , int target , vectorop , vectorinput ,vector&ans ){
if(target == 0){
ans.push_back(op);
return;
}
if(index == input.size()){
return;
}
vectorop1 = op;
vectorop2 = op;
if(target-input[index]>=0){
op1.push_back(input[index]);
solve(index,target-input[index],op1,input,ans);
}
solve(index+1,target,op2,input,ans);
}
vector combinationSum(vector& candidates, int target) {
vectorans;
int index = 0;
vectorop;
solve(index,target,op,candidates,ans);
return ans;
}
};
*Please someone tell me Why this is giving 2 for "axxxy" ?*
For index 1-2 and 2-3
What is the ans for "aaa"?
have to add this to notes
but this question is not matching with the matching algorithm which we used to identify the lcs type??
At 5:20 he clearly starts demonstrating with LCS. And even towards the end, he gives the small difference in code between LCS, and LRS ( i != j is the only extra condition while checking for Longest Repeating Subsequence ).
Great video..👍
But have a doubt that when string :axxxy how the ans:2 ??..
xx gives length 2
Answer would be 1
@@mayankchaudhary5515 2 aayega pagal
@@mayankchaudhary5515 Read Neeraj Jain's comment.
Wah bot tm 6 mhina phle hi pel diya hai isko to.
What about the testcase AABXACBBCZYCC
it should return ABC but as it is repeated thrice...it is returning AABBCC
if the string is just AAA, what should the answer be?
Bro make a playlist on Graph.
great videos
Leaving a time capsule here. Interviews start Dec 1. If you see this after Dec 10, 2021, drop a comment!
Update: I got placed at Unacademy in a Software Engineering role. Thank you Aditya! Your videos helped me a lot in getting my funda straight.
I will too drop right now in 5th sem... Preparing for interviews too
how did they go?
@@kxnyshk It went really well. I got placed at Unacademy in a Software Engineering role :). Thanks for your reply. I had totally forgotten about it. :D
@@amarnathprasad9986 that's amazing. Congrats!
@@kxnyshk Thanks!
I have one doubt If I am using "axxxy" as string its longest repeating subsequence should be 1 because "x" is only repeating but in geeksfoegeeks its output is 2.. HOW???
x->1 and x->2
x->2 and x->3
these are 2 subsequences
@@rohitjoshi6335 but x with index 2 can't be shared so the answer should be 1.
@@akashutreja3233 they can be shared but can't have same position in the other string.
www.geeksforgeeks.org/longest-repeating-and-non-overlapping-substring/ This will give the output you meant.
Bhaiya aapne..... Fibonacci, LIS, kadane's , Dp on grid .....in sb pr videos ni bnai h kya .??
Any one who tried printing longest palindromic substring ??
can someone explain to me, what will be the lrs of axxxy?
I think 1 and that will be "x"
1st sub-seq : "x x" at Index : 1-2
2nd sub-seq: "x x" at index : 2-3
so length = 2;
understood!!
we can also use map for this and make the complexity of O(m+n), and by the way i am fond of your videoes..
Indexes matter in subsequences, lets say u have a string abbbbbbcca. If you just store count of all values, probably u will get abc as answer but abc is occurring only once here.
@@HimanshuKumar-xz5tk but correct answer will be bca
@@Kaivalyamani No, only bbbc
bhaiya graphs par bhi videos banao... please
Awesome
for input abba we need to get 2 na by code i am getting 1
awesome bro ! thank you very much :))
Can't we just put each index in a map where key is the letter. Now for all those letters which have more than one entry in increasing order will be the answer. This will be like linear complexity
what a great question
Bhai DP waali series mein LIS bhool gaya....
Wo bhi nikal de.....
Yeh series dekhne ke baad to DP samaj aari :)
if input = "AAA" it's output should be "A" but it is giving "AA" .please explain
@Aditya Dalvi But if we take 2 A's in 1st subsequence, then we are left with only one A. The repeating subsequence cannot contain a letter at same index. Please Clarify. The output should be only 'A'
@@lohityakumarambashta3921 in the first subsequence "AA" index of first A is 0 and index of second A is 1
whereas in the second subsequence "AA" index of first A is 1 and the index of second A is 2......read twice, position matters, the position of the first index of both subsequences are different(0 and 1) and position of the second index of both subsequences are different(1 and 2).
AA
01
AA
12
I hope this helps you:)
17 SEP 2022