Longest subsequence of one string that is a substring of another

Given two strings x and y, return the length of the longest string t such that:

• t is a subsequence of x: its characters appear in x in the same order, but not necessarily next to each other.
• t is a substring of y: it appears in y as one contiguous block.

If no non-empty t exists, return 0.

def longest_subseq_substring(x: str, y: str) -> int: ...

Constraints

• 0 <= len(x), len(y) <= 1000
• Strings contain lowercase English letters.

Example 1

x = "sunday", y = "saturday"  ->  3

"day" is contiguous in y and appears in order in x (d, a, y). No longer substring of y works: "rday" needs an r, and x has none.

Example 2

x = "axbxcx", y = "zabcz"  ->  3

"abc" skips the x characters in x but is contiguous in y. Plain longest common subsequence is not the same problem: for x = "ab", y = "axb" it gives 2, but the answer here is 1, because "ab" is not contiguous in y.

Be ready to return the matching string itself, and to discuss how the solution changes if x is fixed and many different y strings arrive.