Find longest subsequence of x that is a substring of y
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
Given two strings `x` and `y`, compute the **maximum length** of a string `s` such that:
- `s` is a **subsequence** of `x` (can delete zero or more characters from `x` without reordering the remaining characters), and
- `s` is a **substring** of `y` (must appear as a contiguous block in `y`).
Return the maximum possible length.
### Example
- `x = "abcd"`, `y = "abdc"`
- One optimal choice is `"abd"` (subsequence of `x`, substring of `y`), so the answer is `3`.
### Sample
- `x = "hackerranks"`, `y = "hackers"`
- Output: `7` (because `"hackers"` is a subsequence of `x` and also a substring of `y`).
Overview: This question evaluates string-algorithm skills and conceptual understanding of subsequences versus substrings, along with attention to algorithmic efficiency when relating non-contiguous selections to contiguous patterns.
Given two strings `x` and `y`, compute the **maximum length** of a string `s` such that:
- `s` is a **subsequence** of `x` (you may delete zero or more characters from `x` without reordering the remaining characters), and
- `s` is a **substring** of `y` (it must appear as a contiguous block in `y`).
Return the maximum possible length.
### Example
- `x = "abcd"`, `y = "abdc"` → answer `3`. One optimal choice is `"abd"`, which is a subsequence of `x` and a contiguous substring of `y`.
### Sample
- `x = "hackerranks"`, `y = "hackers"` → answer `7`, because `"hackers"` is a subsequence of `x` and also a substring of `y`.
**Approach.** Every candidate `s` is a contiguous substring `y[i..j]` of `y`. So enumerate substrings of `y` and keep the longest one that is also a subsequence of `x`. Checking whether a string `t` is a subsequence of `x` is a single left-to-right two-pointer scan of `x`. A useful pruning fact: if `y[i..j]` is NOT a subsequence of `x`, then no longer substring starting at the same `i` can be either, so you can stop extending that start index.
Constraints
- 0 <= len(x), len(y)
- Strings consist of printable characters (typically lowercase English letters in the examples).
- The answer is 0 when no character of y appears in x, or when either string is empty.
- The result never exceeds min(len(x), len(y)).
Examples
Input: ("abcd", "abdc")
Expected Output: 3
Explanation: "abd" is a subsequence of x="abcd" and a substring of y="abdc", length 3. No length-4 substring of y is a subsequence of x.
Input: ("hackerranks", "hackers")
Expected Output: 7
Explanation: The whole of y="hackers" is a subsequence of x="hackerranks" (drop the extra r, n, s), so the answer is its full length 7.
Hints
- Every valid s is a contiguous substring of y. Enumerate substrings y[i..j] and test each against x.
- Testing whether a string t is a subsequence of x is a single two-pointer pass: walk through x once, advancing a pointer in t whenever characters match; t is a subsequence iff the pointer reaches the end of t.
- Pruning: if y[i..j] is not a subsequence of x, then no longer substring starting at i can be either — break out of the inner loop. Also skip any candidate whose length is not greater than the best found so far.
Community answers
Answer by rajneesh
Logic (Dynamic Programming)
We use a 2D grid (dp) to track the longest match ending exactly at y[j] using the first i characters of x.
If characters match (x[i] == y[j]): Extend the match.
dp[i][j] = dp[i-1][j-1] + 1
If they don't match (x[i] != y[j]): Skip the character in x (since subsequences allow gaps) and carry the previous best score forward.
dp[i][j] = dp[i-1][j]
The final answer is simply the highest number anywhere in the grid.
The C++ Code
C++```
#include
#include
#include
using namespace std;
int maxLength(string x, string y) {
int n = x.size(), m = y.size(), ans = 0;
vector> dp(n + 1, vector(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (x[i - 1] == y[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i - 1][j];
}
ans = max(ans, dp[i][j]);
}
}
return ans;
}
Complexity
Time & Space: O(n × m) (where n and m are the string lengths). Space can be optimized to O(m) since we only ever look back one row at a time.