Salesforce·Software Engineer·Technical Phone Screen·Intermediate

Suggested Approach

Clarify the problem: we need the longest subsequence of x that appears as a contiguous substring in y. A dynamic programming approach with states (i, j) representing the longest common subsequence ending at x[i] and y[j] can be used, but we must ensure the subsequence is contiguous in y. Alternatively, for each substring of y, find the longest subsequence of x that matches it, but that is inefficient. A more efficient DP: let dp[i][j] be the length of the longest common subsequence of x[0..i] and y[0..j] that ends with x[i] and y[j] (i.e., x[i] == y[j]). Then dp[i][j] = 1 + max(dp[i-1][k] for k < j where x[i-1] matches y[k]? Actually, we need the subsequence to be contiguous in y, so the previous character in the subsequence must come from y at an index less than j, but not necessarily j-1. However, since the subsequence must be contiguous in y, the characters in y that form the subsequence must be consecutive. So if we pick y[j] as the last character, the previous character in the subsequence must be y[j-1]. Therefore, the subsequence in y is a substring, so the indices in y are consecutive. Thus, if we match x[i] to y[j], the previous matched character in x must be some i' < i, and the previous matched character in y must be y[j-1]. So we need to find the longest subsequence of x[0..i-1] that matches y[0..j-1] and ends with y[j-1]? Actually, the subsequence in y is contiguous, so if we match x[i] to y[j], the previous character in the subsequence (if any) must be matched to y[j-1]. So we need to find the longest subsequence of x[0..i-1] that is a substring of y ending at j-1. This suggests a DP where we fix the start of the substring in y. Alternatively, we can think of it as: for each starting position in y, find the longest subsequence of x that matches a prefix of y starting at that position. But that would be O(n*m^2). A better DP: Let dp[i][j] be the length of the longest common subsequence of x[0..i] and y[0..j] that ends with x[i] and y[j] and is contiguous in y. Then dp[i][j] = 1 + max(dp[i-1][j-1] if x[i-1] matches y[j-1]? No, because the previous character in the subsequence must be matched to y[j-1], but x[i-1] may not match y[j-1]. Actually, the previous character in the subsequence is some x[i'] with i' < i, and it must match y[j-1]. So we need to consider all i' < i such that x[i'] == y[j-1] and take the max dp[i'][j-1]. So dp[i][j] = 1 + max_{i' < i, x[i'] == y[j-1]} dp[i'][j-1]. This can be computed efficiently by maintaining for each character the maximum dp value for that character at previous j. So overall O(n*m) time. Then the answer is max over i,j of dp[i][j]. To reconstruct, we can store parent pointers. This is a good approach to present.

Pro tip: Start by clarifying the problem with the interviewer: confirm that the subsequence must be contiguous in y but not necessarily in x, and that we need the length (and optionally the string). Then discuss the DP state and transition, emphasizing the contiguity constraint in y. Mention that a naive approach would be O(n*m^2) but we can optimize to O(n*m) by maintaining the best previous match for each character.