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`).
Quick Answer: 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.