Length of the Longest Common Subsequence
Updated
Problem statement
A subsequence is what remains after deleting zero or more characters from a string. Keep the remaining characters in their original order; they do not need to be next to each other.
For this exercise, given two case-sensitive English-letter strings first and second, return the length of their longest common subsequence. An empty subsequence has length zero.
Function
solution(first: String, second: String) → intExamples
Example 1
first = "ABCBDAB"second = "BDCABA"return = 4BCBA is a common subsequence of length 4, and no longer one exists.
Example 2
first = "XMJYAUZ"second = "MZJAWXU"return = 4MJAU, of length 4, is a common subsequence of both strings.
Example 3
first = ""second = "abc"return = 0This example exercises the empty-string convention: the only common subsequence is empty.
Constraints
- For this exercise, assume
0 <= first.length, second.length <= 1000. - For this exercise, assume both strings contain only uppercase and lowercase English letters, compared case-sensitively.
More Marshall Wace interview questions
- Count Letters with Ordered Lowercase and Uppercase OccurrencesOA · Seen Oct 2025
- Maximum Trailing Zeros on a Path with at Most One TurnOA · Seen Oct 2025
- Shortest Subarray Covering an Integer RangeOA · Seen Oct 2025
- Maximum Sum with at Most Three Two-Element TilesPHONE SCREEN · Seen Sep 2025
- Minimum Full Glasses for an Exact Water VolumePHONE SCREEN · Seen Sep 2025
- Smallest Absolute Difference Between Two Array ElementsPHONE SCREEN · Seen Sep 2025
- Maximum Events in a 60-Second WindowOA · Seen Aug 2025
- Successful Logins from Multiple CountriesOA · Seen Aug 2025
- Maximize Remaining Item Types After Clearing Consecutive ShelvesOA · Seen Nov 2024
- Shortest String After Erasing Equal PairsOA · Seen Nov 2024
Similar questions at other companies
- Maximum Bouquet ValueOracle · ONSITE INTERVIEWOracle interview questions
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Word BreakGoogle · ONSITE INTERVIEWGoogle interview questions
- Reconstruct One Sentence From a DictionaryMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Scramble StringExpedia · ONSITE INTERVIEWExpedia interview questions
- Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Decode Numeric StringArcesium · ONSITE INTERVIEWArcesium interview questions
- Word BreakBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Count Vowel PermutationsZscaler · ONSITE INTERVIEWZscaler interview questions