Longest Subsequence which is a Substring
Updated
Problem statement
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.
Function
longestSubsequenceWhichIsSubstring(x: String, y: String) → int
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).
Examples
Example 1
x = "abcd"y = "abdc"return = 3
The subsequence "abd" is present in x and also appears as a substring in y.
Example 2
x = "hackerranks"y = "hackers"return = 7"hackers" is a substring of y and also a subsequence of x, so the answer is 7.
Constraints
1 <= x.length, y.length <= 2000xandycontain lowercase English letters.
More Salesforce Online Assessment questions
- Count Subarrays With Product Equal to KOA · Seen Nov 2026
- Minimum No-Repeat Segments After One Character RemovalOA · Seen Nov 2026
- Get Message StatusOA · Seen Nov 2026
- Minimum Unique-Character Segments After DeletionOA · Seen Sep 2026
- Run-Length String CompressionOA · Seen Sep 2026
- Maximum Requests in WindowOA · Seen Sep 2026
- Final Pod Counts After LogsOA · Seen Aug 2026
- Minimum Removals to Balance ArrayOA · Seen Aug 2026
- Is This Date a Weekend?OA · Seen Aug 2026
- Maximum Barbell WeightOA · Seen Jul 2026
Similar questions at other companies
- Longest Subsequence That Is a SubstringExpedia · OAExpedia interview questions
- Longest Properly Closed Bracket RunAdobe · PHONE SCREENAdobe interview questions
- Indexed Proximity SearchStripe · PHONE SCREENStripe interview questions
- Longest Palindromic SubstringSiemens · PHONE SCREEN
- Longest Palindromic SubstringIBM · PHONE SCREENIBM interview questions
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Longest Palindromic Substring LengthMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Longest Palindromic SubstringGoogle · ONSITE INTERVIEWGoogle interview questions
- Longest Palindromic SubstringInMobi · PHONE SCREENInMobi interview questions
- Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions