Longest Repeating Subsequence — Problem & Solution
Longest Repeating Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Longest Repeating Subsequence is a medium coding problem on strings and dynamic programming, asked in Amazon, Microsoft and Paytm interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Microsoft, Paytm
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, find the length of the longest subsequence that occurs twice in s such that the two occurrences never use the same position for the same character.
Formally, you need two increasing index sequences i1 < i2 < … < iL and j1 < j2 < … < jL with s[ia] == s[ja] and ia != ja for every a. The two sequences may otherwise share positions. Return the largest possible L; if no character repeats, the answer is 0.
Example 1
Input: s = "axxzxy"
Output: 2
Explanation: "xx" occurs at indices (1, 2) and (2, 4): at each step the two occurrences use different positions.
Example 2
Input: s = "aabb"
Output: 2
Explanation: "ab" occurs at (0, 2) and (1, 3).
Example 3
Input: s = "abc"
Output: 0
Explanation: No character appears twice.
Constraints
1 <= s.length <= 1000s consists of lowercase English letters
Hints for Longest Repeating Subsequence
Hint 1
Think of matching
sagainst a copy of itself, like the longest common subsequence of two strings.Hint 2
The one extra rule: a character may not be matched with itself — position
iin the first copy may not pair with positioniin the second.Hint 3
Run the LCS table on
(s, s)and only take the diagonal stepdp[i-1][j-1] + 1whens[i-1] == s[j-1]andi != j.
How to solve Longest Repeating Subsequence
Two occurrences of a subsequence in s are a common subsequence of s and s whose matched positions differ pairwise. So it is the longest common subsequence of the string with itself, forbidding a match of a position with itself.
Approach
- Create
dp[0..n][0..n]of zeros. - For
i, jfrom 1 ton: ifs[i-1] == s[j-1]andi != j,dp[i][j] = dp[i-1][j-1] + 1; otherwisedp[i][j] = max(dp[i-1][j], dp[i][j-1]). - Return
dp[n][n].
Why it works
dp[i][j] is the longest pair of occurrences drawn from prefix s[0..i) for the first and s[0..j) for the second, with no position paired to itself. The usual LCS argument applies — the last characters either pair together or one of them is unused — and the i != j test excludes exactly the forbidden self-pairing.
Complexity
- Time —
O(n^2) - Space —
O(n^2) (O(n) with two rows)
Pitfalls
- Without the
i != jtest, every string's answer would ben(the string matches itself). - The two occurrences may share positions as long as they never share the same position at the same step: in "axxxy" the answer is 2 ("xx" at (1,2) and (2,3)).
- This is a subsequence problem, not a substring one — characters need not be adjacent.
Reference solution
Python
def longestRepeatingSubsequence(s: str) -> int:
n = len(s)
prev = [0] * (n + 1)
for i in range(1, n + 1):
cur = [0] * (n + 1)
ci = s[i - 1]
for j in range(1, n + 1):
if ci == s[j - 1] and i != j:
cur[j] = prev[j - 1] + 1
else:
cur[j] = prev[j] if prev[j] > cur[j - 1] else cur[j - 1]
prev = cur
return prev[n]Java
public static int longestRepeatingSubsequence(String s) {
int n = s.length();
int[] prev = new int[n + 1], cur = new int[n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j && s.charAt(i - 1) == s.charAt(j - 1)) cur[j] = prev[j - 1] + 1;
else cur[j] = Math.max(prev[j], cur[j - 1]);
}
int[] t = prev; prev = cur; cur = t;
}
return prev[n];
}C++
int longestRepeatingSubsequence(string s) {
int n = s.size();
vector<int> prev(n + 1, 0), cur(n + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j && s[i - 1] == s[j - 1]) cur[j] = prev[j - 1] + 1;
else cur[j] = max(prev[j], cur[j - 1]);
}
swap(prev, cur);
}
return prev[n];
}JavaScript
var longestRepeatingSubsequence = function(s) {
var n = s.length;
var prev = new Array(n + 1).fill(0);
var cur = new Array(n + 1).fill(0);
for (var i = 1; i <= n; i++) {
for (var j = 1; j <= n; j++) {
if (i !== j && s.charCodeAt(i - 1) === s.charCodeAt(j - 1)) cur[j] = prev[j - 1] + 1;
else cur[j] = Math.max(prev[j], cur[j - 1]);
}
var t = prev; prev = cur; cur = t;
}
return prev[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming