For MTS role
You are given two strings x and y. You need to find the length of the longest subsequence of x that is also a substring of y.
A subsequence is a sequence derived from another string by deleting some or no elements without changing the order.
A substring is a contiguous part of a string.
Complete the function longestSubsequenceWhichIsSubstring in the editor.
longestSubsequenceWhichIsSubstring has the following parameters:
String x: the first stringString y: the second string
Returns
int: the length of the longest subsequence of x that is also a substring of y
Approach
I generated all substrings of y and checked if they are subsequences of x.
Used a helper function for checking subsequence in O(M) time using two pointers.
Time complexity: O(N² * M), where N = len(y), M = len(x).
x = "abcd" y = "abdc" return = 3
x and also appears as a substring in y.x = "hackerranks" y = "hackers" return = 7
"hackers" is a substring of y and also a subsequence of x, so the answer is 7.
1 <= x.length, y.length <= 2000xandycontain lowercase English letters.
- Count Prime StringsONSITE INTERVIEW · Seen Jun 2026
- Key Teams in TreeOA · Seen Mar 2026
- System Energy ReductionOA · Seen Mar 2026
- Update Logs by Symmetric XOROA · Seen Mar 2026
- Count Palindromic Concatenation PairsOA · Seen Mar 2026
- Collect Opportunity Data in a TreeOA · Seen Feb 2026
- Replace '?' to Avoid Adjacent DuplicatesOA · Seen Feb 2026
- Strings With No k Consecutive Identical CharactersOA · Seen Feb 2026
public int longestSubsequenceWhichIsSubstring(String x, String y) {
// write your code here
}