Longest Repeating Subsequence

Medium
1609.

Longest Repeating Subsequence

Longest Repeating Subsequence is a medium coding problem on strings and dynamic programming, asked in Amazon, Microsoft and Paytm interviews.

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 <= 1000
  • s consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var longestRepeatingSubsequence = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • s consists of lowercase English letters

Hints for Longest Repeating Subsequence

  1. Hint 1

    Think of matching s against a copy of itself, like the longest common subsequence of two strings.

  2. Hint 2

    The one extra rule: a character may not be matched with itself — position i in the first copy may not pair with position i in the second.

  3. Hint 3

    Run the LCS table on (s, s) and only take the diagonal step dp[i-1][j-1] + 1 when s[i-1] == s[j-1] and i != 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

  1. Create dp[0..n][0..n] of zeros.
  2. For i, j from 1 to n: if s[i-1] == s[j-1] and i != j, dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  3. 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 != j test, every string's answer would be n (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