Hello! Today we’ll be looking at another DP question. This is a variation of LCS and a slight modification of LCS will hold.
Longest Repeated Subsequence is a subsequence of a string such that it appears twice but those two identical subsequences DO NOT have any same character at the same position. Let’s take an example, consider “AAEFBB”.
-> A A E F B B
-> A A E F B B
AB is a subsequence of “AAEFBB” which appears “twice” in the original string but they do not have any overlapping index.
Longest Common Sequence(LCS) can be used to find the LRS. Recall that LCS is a common subsequence of two strings with the maximum length. As you can notice from the example above, finding the LRS is simply finding the LCS but with no characters at the same position of the two strings.
The code below will give you clear ideas
Time Complexity: O(n²)
The only difference is line 10 . When i==j, skip it.
[Contact Info]
email: changjin9792@gmail.com
![[Leetcode] #1008 Construct Binary Search Tree from Preorder Traversal(C++/Tree/Medium)](https://miro.medium.com/v2/resize:fit:679/1*I4RG2CAiBIgoq31AVqJV2Q.jpeg)
![[Algorithm] Leetcode #91 Decode Ways (DP/Medium/C++) — How to solve ANY DP](https://miro.medium.com/v2/resize:fit:679/1*Dl0F36mQqB_LNtA_dKd3ug.jpeg)
![[Algorithm] Longest Common Substring (C++/DP/Medium)](https://miro.medium.com/v2/resize:fit:679/1*yuVzMhCJyDENbyhwAsrkwA.png)
