What is the brute force approach and complexity for Longest Repeating Subsequence?

Two pointers walk through s: match when the letters agree at different indexes, else skip one with time complexity O(2^(2N)) and space complexity O(N).

What is the optimal approach and complexity for Longest Repeating Subsequence?

The same table in two rows; the diagonal (i = j) is never a match with optimal time complexity O(N²) and space complexity O(N).

Longest Repeating Subsequence

Q: How do you identify the pattern for Longest Repeating Subsequence?

Look for key signals in the prompt: "subsequence" indicates Letters can be skipped in each copy, so the rule is LCS-like, not a repeated substring.; "appears twice in s" indicates The answer is the LCS of s with itself, so the table compares two positions in the same string.; "a letter cannot be used at the same place in both copies" indicates The diagonal (i = j) is forbidden: that is the one change to the LCS rule..

Medium·GeeksforGeeks Pro OnlySlight Variation

GeeksforGeeks

Problem Statement

You are given a string s. Find the length of the longest subsequence that can be found twice in s. Two copies are picked from s by deleting letters. A letter from one place in s can be used by both copies, but only when it sits at different places inside the two copies. Return the length of the longest such subsequence.

Input

A string s.

Output

The length of the longest subsequence that can be picked twice from s under the rule above.

Example 1

Input: s = "axxzxy"

Output: 2

xx appears twice. One copy uses indexes 1 and 2. The other uses indexes 2 and 4. Index 2 is in both copies, but it is the second letter of one copy and the first letter of the other, so it is allowed.

Example 2

Input: s = "axxxy"

Output: 2

Again xx. One copy uses indexes 1 and 2, and the other uses indexes 2 and 3. Index 2 is shared at different places.

Constraints

• 1 ≤ s.length ≤ 1000

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“subsequence”

→ Letters can be skipped in each copy, so the rule is LCS-like, not a repeated substring.

“appears twice in s”

→ The answer is the LCS of s with itself, so the table compares two positions in the same string.

“a letter cannot be used at the same place in both copies”

→ The diagonal (i = j) is forbidden: that is the one change to the LCS rule.

Approach Complexity Ladder

Brute Force — recursion on two positions in sO(2^(2N))O(N)

Two pointers walk through s: match when the letters agree at different indexes, else skip one

Better — a full table over prefixes of sO(N²)O(N²)

dp[i][j] for every pair of prefixes; a match needs i ≠ j

Optimal — two rows: the row above and the row being filledO(N²)O(N)

The same table in two rows; the diagonal (i = j) is never a match

Brute Force Intuition

Let f(i, j) be the answer when copy A may still use s[i..] and copy B may still use s[j..]. If i ≠ j and s[i] = s[j], the pair can be used as the next letter of both copies: 1 + f(i+1, j+1). Otherwise skip the next letter of one copy: max(f(i+1, j), f(i, j+1)).

Recognition rule for this sub-pattern:

Match → 1 + dp[i−1][j−1]; otherwise max(dp[i−1][j], dp[i][j−1]). Counting versions add the cases instead of taking a max.

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture