Maximum Length Subsequence Substring
You are given two strings, x and y. Return the longest string that is both a subsequence of x and a contiguous substring of y.
A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. A substring consists of consecutive characters.
If multiple valid strings have the maximum length, return the lexicographically smallest one. If no non-empty valid string exists, return an empty string.
Method Signature
String longestSubsequenceSubstring(String x, String y)
x is the string from which the result must be obtainable as a subsequence.y is the string in which the result must appear as a contiguous substring.- The method returns the longest string satisfying both conditions.
Deterministic Selection
When multiple valid strings have the same maximum length, compare them lexicographically and return the smallest string.
Constraints
1 ≤ x.length() ≤ 2,0001 ≤ y.length() ≤ 2,000x and y contain only lowercase English letters.
Examples
Example 1
longestSubsequenceSubstring(x = "abcde", y = "zbcxy")
Output: "bc"
The string "bc" is a subsequence of x and appears consecutively in y. No longer valid string exists.
Example 2
longestSubsequenceSubstring(x = "axbxcxd", y = "zzabcdyy")
Output: "abcd"
The string "abcd" is a subsequence of x and a substring of y.
Example 3
longestSubsequenceSubstring(x = "cabd", y = "abca")
Output: "ab"
Both "ab" and "ca" are valid strings of length 2. The method returns "ab" because it is lexicographically smaller.
Example 4
longestSubsequenceSubstring(x = "abc", y = "xyz")
Output: ""
The two strings have no common character, so no non-empty valid string exists.