30 Longest repeating subsequence

[@eren-qu9uu]

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.

[@oaarian2014]

untouchables ..dank bhai😂😂

[@thorxn1382]

Is it funny

[@nikhilraj5115]

Bro ,do you have any plan to publish the series on "graph".

[@Prince-fz6yo]

@OttoLyle @Mauricio Weston.. u both seems to be of same mother but diff fathers

[@tushargupta6336]

no

[@RuinsOfTheUnknown]

@@Prince-fz6yo 😂😂😂😂

[@arafatkhan5489]

@@maharajak6578 bhai this weston dude's comment got deleted ig, what did he say tho?

[@SHASHANKRUSTAGII]

@@arafatkhan5489 haha i also didnt get

[@HarpreetSingh-mb2rk]

literally the logic of this problem comes to my mind automatically after watching your DP playlist.

[@ankitbhardwaj9566]

please make more videos on weighted graphs ,shortest paths ,prim ,krushkal ,,from codeforces

[@jain007neeraj]

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.

[@hemantmangwani1006]

Case :- AABCABB ANS :- 5 This question is little bit confusing read it twice if anyone is confused.

[@DeepakKumar-yl3ok]

@@hemantmangwani1006 The answer should be 4 for the string "AABCABB" not 5

[@koustav6884]

@@DeepakKumar-yl3ok yes

[@bhaswatraj9433]

RAJ Kumar why is it not 3

[@koustav6884]

@@bhaswatraj9433 No answer will be four you can cross check it by applying on algorithm

[@mukeshranjanmallick8832]

Whole Series is just awesome , Great explanation and thought process

[@travellingsLenses]

Amazingly explained bro. Itne easy-going flow me samjhaya hai ki Binge watching chal rhi hai :D

[@AJ-gg1jc]

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.....

[@vivekmishra641]

I relinquished the idea of taking the second string similar to first one due to the same reason.

[@0anant0]

29 of 50 (58%) done! Very nicely done!

[@pr1493]

It doesn't mean that you achieved something here, hold back and practice

[@prateekchauhan5376]

@@pr1493 if u cant support, atleast don't be toxic

[@pr1493]

@@prateekchauhan5376 Just tried to push that guy to practice more without getting complacent, Don't know what ails you here lol 😂

[@deepakpandey3485]

@@pr1493 jada cool mat ban bhai... tune kya kiya you also know it.

[@pr1493]

@@deepakpandey3485 We can talk when you have a job

[@vakhariyajay315]

Thank you very much. You are a genius.

[@lalit2926]

Oh !! my bad, both strings are equal😂😂 @5:50 .. .. .. By the way your DP tutorial is best sir❤❤..

[@umashankarpanigrahi]

haha

[@g1patil]

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 !!

[@shivanidalmia2623]

Can you make a video on Longest Increasing subsequence.

[@anandabhinav]

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! 😎

[@maximus6448]

@@anandabhinav If there will be repitition in array it will give wrong ans

[@anandabhinav]

@@maximus6448 bro binary search wala approach use karrlenge phirr.

[@VIVEK1898]

@@yashbhanushali8456 remove duplicates from the sorted array.

[@VIVEK1898]

@@anandabhinav remove duplicated from sorted array

[@shritvaagarwal614]

Simply Genius!!...........Please bring graph series too

[@saurabhmodi5128]

best explanation of the Longest repeating subsequence

[@supriyakvs]

For string AAABA, the longest repeating subsequence is AAA. Because we can form AAA using 2 options here position 0,1,2 and position 1,2,4. Here, Characters are same but positions are different. That is what is mentioned in the question. I struggled with this because i thought it should be AA only. Hope this helps someone reading comments for clarification.

[@saranghae3720]

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...

[@paveshkanungo6338]

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

[@dhruvagarwal646]

We can also do for(int i=1; i

[@kshitiz5621]

why ?

[@dhruvagarwal646]

@@kshitiz5621 Because you can't use the same character in the repeating sequence.

[@pranjaltiwari2344]

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......

[@hemantmangwani1006]

Ya you are right.

[@ayansrivastava722]

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.

[@Rohan-vl1ve]

Thank you bro, you have great teaching and explaining skills

[@pawankumarpandit1822]

thank you aditya bhaiya because of you i am able to solve the different kind of question

[@sanyamsinghal7992]

lovely explanation!! great work man ♥♥ please also make videos on graph topics like BFS, DFS and Shortest path.

[@TheAdityaVerma]

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 !! ✌️❤️

[@abhijitburman1260]

@@TheAdityaVerma next video kab aayega bhaiya??

[@krishnasai3367]

@@TheAdityaVerma its been more than a year, still no videos on graphs 😔😭

[@Vishal-ds6ly]

@@TheAdityaVerma its been than 2 year, still no videos on graphs.

[@sidhantjha4566]

@@TheAdityaVerma We Want Graph Series.

[@sumitkumar-oi5vq]

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 :)

[@vineetchaurasia6600]

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

[@vineetchaurasia6600]

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]

[@gunjanshinde396]

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.

[@bhatanand]

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 }

[@chamangupta4624]

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

[@vladimirputin2756]

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); } }

[@samarthbhawsar8739]

Amazing Explanation🙌🙌 It's just like a magic happened in every video..👏👏🔥🔥

[@hustler516]

Bhaiya lol to ur teaching 🥰 ......who else wants to say the same lines to bhai with me

[@siddheshjain8677]

This was a very good question solved in an easiest manner ever!

[@aniket6858]

Bro we got AABBDD on taking all these conditions in mind.. shouldn't we do half of it to get final answer??

[@nikhilranjan7126]

Awesome content I am waiting for more such videos... your explanation is good.

[@samriddhashukla5345]

bhai chota sa question itna complicate kiya aapne maza aa gya

[@aayush1204]

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 😀

[@thinkingmad1685]

Have you found any series like this for dp on grids, lis Or even understandable in yt pls suggest me 😔

[@lovedeepsingh120]

@@thinkingmad1685 Watch Striver's DP playlist for these topics. He explained all of them very well..

[@amarnathprasad1]

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.

[@MilindGupta]

I will too drop right now in 5th sem... Preparing for interviews too

[@kxnyshk]

how did they go?

[@amarnathprasad1]

@@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

[@kxnyshk]

@@amarnathprasad1 that's amazing. Congrats!

[@amarnathprasad1]

@@kxnyshk Thanks!

[@ShivamSharma-bb1jx]

faad diya bro faad diya.....!!

[@ManishYadav-eg4bl]

Hn bhai.😅

[@oqant0424]

Amazing Explanation🙌🙌

[@abhi-5783]

"Untouchables hai, nahi hai...". Lol

[@AkashKumar-vc5yl]

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.

[@meenasharma9280]

but what about order try ABBAC

[@23cash86]

before 10:00 for explanation.....12:00 for final answer ...bookmark for me XD

[@SilentNight_Tour]

MZA AA GYA DP SEIES SIR

[@Education_2753]

Sir plz complete this playlist of dynamic programming It's humble request sir plz Upload the video sir as soon as possible

[@AMITKUMAR-ze9yo]

thanks buddy :) , @5:50 leaving 'e' while finding LCS of same string was funny though :D

[@rahulchudasama9363]

Hi Aditya, Big thank you, Can you please make a playlist of the graph ???

[@samyakjain720]

Bhai u made dynamic programming like sweet

[@ngtv5608]

Need a playlist on GRAPH !!

[@rhythemjain1067]

You should try Striver's Graph series. It really helped me in clearing my concepts.

[@princenagar1686]

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.

[@sushanthg6573]

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 🙏

[@chamangupta4624]

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?

[@PeaceLoveAman]

last me jo output aayega usko 2 se divide bhi karna padega na ?

[@kshitijgaur9635]

yess

[@PeaceLoveAman]

@@kshitijgaur9635 job lag gayi ab jarurat nahi😂😂

[@kshitijgaur9635]

@@PeaceLoveAman Congratulations bro!!!!

[@rashmirathore6623]

Nice explanation

[@aniketkumarsinha2537]

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

[@riyaprasad5904]

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 .

[@pruthvirajk6019]

Awesome..No words....

[@TheAdityaVerma]

Thank you so much 😀

[@iitianashishmadhukar9861]

great explain thanks you

[@shreeniwasdeshpande6394]

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 .

[@ramabhiramabhi97]

Bro the code using hashmap cannot gurantee about the subsequence. Correct me if i am wrong

[@shashishekhar1729]

it wont work try for this : ABADDBE

[@apoorv7361]

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 ??

[@subhamengine1143]

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; } };

[@SudhanshuKumar-lp1nr]

AC kaise hua example, qki AC me toh C repeat kr rahi hai 2:40

[@YashSharma-dz7uu]

If you wanr to print : (Including both methods - Recursion and top-down ) #include #include #include #include #include #include using namespace std; stack st; set S; int ans(string s1, string s2, int n, int m) { if (n == 0 || m == 0) { return 0; } if (s1[n - 1] == s2[m - 1] && n != m) { return 1 + ans(s1, s2, n - 1, m - 1); } return max(ans(s1, s2, n, m - 1), ans(s1, s2, n - 1, m)); } int main() { string s1, s2; cin >> s1; s2 = s1; int l1 = s1.size(); int l2 = s2.size(); int t[l1 + 1][l2 + 1]; for (int i = 0; i

[@abbas.muzammil23]

Hey, we should compare the given string itself, right? No need to reverse the given string and compare.

[@shreyasvishwakarma8979]

Can't we use directly UNORDERED MAP ??? We will ignore those elements which occurred only once. PLEASE CLARIFY MY DOUBT

[@gautamarora6516]

We can do that, definitely

[@KamalSharma-ep7mj]

6:37 untouchables h? 💀

[@AyushGupta-ux4gq]

😆😆😆

[@parthvasoya665]

At 2:16, How does "AC" occur 2x times in the input "AABEBCDD"? Although "A" is there 2 times, "C" only occurs once, and by definition, we can't select the exact same set of letters for another occurrence. It also happens to violate the definition given in one of the comments (by @jain007neeraj): "Given a string, print the longest repeating subsequence such that the two subsequences don’t have same string character at same position" Here, "C" occurs at the 1st index(second character) in both cases, i.e., 'XC' and 'YC' where X and Y are two different "A" characters. Please let me know if I am missing any concept or if my assumption is wrong in any sense. Thanks in advance.

[@VipulGaur3]

He gave 'AC' just as an example, that it might have been another repeating subsequence if the string were a bit different.

[@pranshunema6719]

Completely agree.. AC doesn't follows the condition

[@anshumansrivastava8108]

so if we will remove the unique characters from the string that should do the work?

[@AmitSingh-cs2hb]

Nope,as in subsequence order also matters

[@pranjalbansal8459]

@@AmitSingh-cs2hb I think it will work fine if we want to count the size because in counting size the order does not matters

[@bharatjoshi1473]

@@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 .

[@bhushanbhosale2394]

What if the series is ABCDDCBA the longest repeating subsequence is just DD not ABCD So will this code run?

[@RajatGupta-lq3cb]

won't LRS be "D" and not "DD"?

[@kxnyshk]

@@RajatGupta-lq3cb yes, only "D"

[@venkatarohitpotnuru38]

for input abba we need to get 2 na by code i am getting 1

[@Dipakjadhav]

@Aditya Verma where are you? Why you are nit uploading videos?

[@sehajmakkarr]

6:36 legendary

[@kathanadalaja]

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?

[@saurabhsen3560]

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???

[@rohitjoshi6335]

x->1 and x->2 x->2 and x->3 these are 2 subsequences

[@akashutreja3233]

@@rohitjoshi6335 but x with index 2 can't be shared so the answer should be 1.

[@rohitjoshi6335]

@@akashutreja3233 they can be shared but can't have same position in the other string.

[@AshutoshSingh-qj1gm]

www.geeksforgeeks.org/longest-repeating-and-non-overlapping-substring/ This will give the output you meant.

[@akashbhoi1951]

What is the ans for "aaa"?

[@kanhav03]

Will it work for input such as AABBDDABD where the output should be 3 Mine giving o/p as 4

[@satyalakshmiyeleti1149]

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

[@kanhav03]

@@satyalakshmiyeleti1149 where will i find the 2nd ABDD there is only one ABDD in the string

[@satyalakshmiyeleti1149]

@@kanhav03 at index 1 3 5 8 : A B D D respectively

[@divineforever8691]

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......

[@divineforever8691]

update: i misunderstood problem:((((

[@Unknown-Stranger]

@@divineforever8691 LOLOLOLOLOLOLOLOLOL

[@niru1931]

nice explanation

[@TheAdityaVerma]

Thanks!

[@035_shubhamsaurav5]

Great video..👍 But have a doubt that when string :axxxy how the ans:2 ??..

[@akshatpandey2256]

xx gives length 2

[@mayankchaudhary5515]

Answer would be 1

[@AmitSingh-cs2hb]

@@mayankchaudhary5515 2 aayega pagal

[@0anant0]

@@mayankchaudhary5515 Read Neeraj Jain's comment.

[@yelp9359]

Wah bot tm 6 mhina phle hi pel diya hai isko to.

[@rishabhyadav8269]

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 ?

[@devangrajarora7002]

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.

[@bikashsah6338]

gazab ka explanation .......

[@roushanraj8530]

Bhaiya aapne..... Fibonacci, LIS, kadane's , Dp on grid .....in sb pr videos ni bnai h kya .??

[@ArghyaBhattacharyaNITA]

Bhai.. Can you arrive to the point faster. I am at 8:25 and still no sign of the solution.

[@TheAdityaVerma]

Honestly if you are looking for fast quick solutions with no concepts/relation building - this is not the channel you should be watching :) That being said, I will try to keep that feedback in mind but no promises :)

[@divyanshsrivastava7150]

@@TheAdityaVerma wohoo you are still active on this channel

[@RandomShowerThoughts]

if the string is just AAA, what should the answer be?

[@ShubhamKumar-jd8bk]

*Please someone tell me Why this is giving 2 for "axxxy" ?*

[@kxnyshk]

For index 1-2 and 2-3

[@Pratik-Kedar]

Any one who tried printing longest palindromic substring ??

[@chethan_madhu_vlogs]

Bro can you give solution for longest repeating substring?

[@kiwimoma1799]

we need series for graph T.T

[@ekanshgoyal6714]

Bhai DP waali series mein LIS bhool gaya.... Wo bhi nikal de..... Yeh series dekhne ke baad to DP samaj aari :)

[@harshitjain9551]

@Aditya Verma For AABBEBCDD its not working in this B comes thrice and giving us wrong output

[@youtubecr3115]

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.

[@shubhamsom]

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?

[@ashishchawla2718]

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.

[@shubhamsom]

@@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

[@sushilsingh9632]

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?

[@devanshjha5836]

AB will not be a subsequence here since the order is not maintained

[@ashishdas4784]

Nice one , but we can extract the repeating character from the LCS by using hash map if I am not wrong

[@fetkamausam5132]

Same thought

[@vineetjain7518]

HashMap do not preserve the order

[@sushmitagoswami2033]

@@vineetjain7518 we can have a list of indexes in the value part of the map?

[@vineetjain7518]

@@sushmitagoswami2033 it will throw an exception as from list an element can be removed add at any specific position therefore compile time error

[@Your_Boy_Suraj]

Python Code Solution: class Solution: def LongestRepeatingSubsequence(self, str): return longestRepeatingSubsequence(str, str, len(str), len(str)) def longestRepeatingSubsequence(X, Y, n, m): dp = [[-1 for i in range(m+1)] for j in range(n+1)] for i in range(n+1): for j in range(m+1): if i==0 or j==0: dp[i][j] = 0 for i in range(1, n+1): for j in range(1, m+1): if(X[i-1] == Y[j-1] and i != j): dp[i][j] = 1 + dp[i-1][j-1] else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[n][m]

[@rajaryan7576]

Lcs of S1 & S2 will be s itself, then what is the point of finding lcs? And i==j will always be true....

[@gauravraj2604]

what should be output of axxxy? If anyone can explain?

[@ShubhamSingh-gw9kq]

Awesome yrr!!!

[@TheAdityaVerma]

Thanks brother, Do subscribe and share, that keeps me motivated to do more !!

[@arpangoyal9947]

We can also do these question using frequency mapping

[@AmanKhandelwal07]

What will be the answer for BAABDD

[@ShubhamKumar-jd8bk]

2 BD with index 0 and 4 second BD with index 3 and 5

[@aryannijhawan8448]

have to add this to notes

[@deepakbijani5495]

find longest palindrom length and divide it by 2

[@saivamsi8400]

No bro i think this won't work because if you consider the string "ABCKZABC" the lps is not abcabc but the longest repeating subsequence is!

[@pranjalshinde1586]

What about the testcase AABXACBBCZYCC it should return ABC but as it is repeated thrice...it is returning AABBCC

[@apnapython]

great videos

[@ankurgupta4696]

but this question is not matching with the matching algorithm which we used to identify the lcs type??

[@raghuwanshiaru]

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 ).