Longest Echoed Subsequence
Medium2-D Dynamic Programming
Problem
An audio engineer looks for an echo in a signal encoded as the string s: a sequence of characters that can be read as a subsequence of s twice, using two index sequences that never use the same position at the same step. (The two readings may share positions at different steps.)
Formally, find the largest k with indices i1 < i2 < … < ik and j1 < j2 < … < jk such that s[it] == s[jt] and it != jt for every t. Return k.
Example 1
- Input:
- s = "aabb"
- Output:
- 2
"ab" can be read as positions (0, 2) and (1, 3).
Example 2
- Input:
- s = "abc"
- Output:
- 0
Every character appears once, so nothing can be read twice.
Example 3
- Input:
- s = "axxxy"
- Output:
- 2
"xx" as positions (1, 2) and (2, 3): position 2 is used by both readings, but at different steps.
Constraints
- 1 ≤ s.length ≤ 1000
- s contains lowercase English letters only.
Hint
Show the first hint
Two readings of the same string, matched step by step: does that remind you of a common subsequence between two strings?
Walkthrough
How to approach it
01Clarify before coding
- May the two readings share a position? Yes, as long as it is not at the same step (the third example uses position 2 twice).
- Is the answer 0 when every character is unique? Yes.
- Length only? Yes.
02Brute force
Try every subsequence and test whether it can be embedded twice with differing positions at each step.
Cost: Exponential: 2^n candidates, each with its own matching search.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.