Practice Expedia Coding Question | Real Coding Interviews

Quick Summary

Find the maximum length of a string that acts as both a subsequence of x and a contiguous substring of y.
Requires simultaneously tracking non-contiguous matches in one string and contiguous matches in another.
Solved efficiently using dynamic programming with a custom state transition.

What This Tests

Dynamic Programming state definition and transitions
Handling multiple overlapping constraints on strings
Optimizing time and space complexity for grid-based DP

Common Patterns

Dynamic Programming

(This question is a variation of the LeetCode question 1143. Longest Common Subsequence. If you haven't completed that question yet, it is recommended to solve it first.)

Given two strings x and y, return the length of the longest subsequence of x that is also a substring of y. If no non-empty match exists, return 0.

Test Cases

Input

Output

Expected