Longest Subsequence That Is a Substring
Booking.com● MediumFULLTIMEOAProblem statement
Find the longest string that is both a subsequence of x and a contiguous substring of y. Return its length.
A subsequence may skip characters of x while keeping their order. A substring must use consecutive characters of y. Return0 if either input is empty or no nonempty string qualifies.
Function
longestSubsequence(x: String, y: String) → intExamples
Example 1
x = "abcd"y = "abdc"return = 3The string abd is a subsequence of abcd and the first three consecutive characters of abdc. Length4 would require all of abdc, whose d-before-c order is not a subsequence of abcd. Therefore the maximum length is3.
Constraints
- 0 <= x.length <= 2000.
- 0 <= y.length <= 2000.
- x and y contain only lowercase English letters.