Longest Common Subsequence
Updated
Problem statement
Given strings text1 and text2, return the length of their longest common subsequence.
A subsequence is obtained by deleting zero or more characters without changing the order of those retained. Its characters do not need to be contiguous. For this exercise, return 0 if either string is empty or if no nonempty common subsequence exists. Return the maximum length, not the number of possible subsequences.
Function
lcsLength(text1: String, text2: String) → intExamples
Example 1
text1 = "abxyzcd"text2 = "acbd"return = 3The subsequence abd appears in both strings and has length 3. A length 4 match would have to equal all of acbd, but c appears after b in text1, so acbd is not a subsequence of it. Therefore 3 is optimal.
Example 2
text1 = "abc"text2 = "def"return = 0The two strings share no character, so their only common subsequence is empty and the result is 0.
Constraints
- For this exercise, assume 0 <= text1.length <= 500.
- For this exercise, assume 0 <= text2.length <= 500.
- For this exercise, both strings contain only lowercase ASCII letters a through z.
More Morgan Stanley Online Assessment questions
- Three-Resource 0/1 KnapsackOA · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Maximum Total of Nonadjacent RatingsOA · Seen Jul 2026
- Count Shipment SchedulesOA · Seen Apr 2026
- Delete and EarnOA · Seen Apr 2026
- Interleave Array HalvesOA · Seen Apr 2026
- Get Patch SequenceOA · Seen Feb 2025
- String Subsequences 🐳OA · Seen Mar 2024
- Binary Tree Level OrderOA · Seen Feb 2024
- Merge IntervalsOA · Seen Feb 2024
Similar questions at other companies
- Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
- Longest Subsequence That Is a SubstringBooking.com · OA
- Count Digit Replacements with No Equal Adjacent DigitsMicrosoft · OAMicrosoft interview questions
- Palindrome CounterGoldman Sachs · OAGoldman Sachs interview questions
- Longest String ChainVisa · OAVisa interview questions
- Minimum-Cost Digit String DecodingSquadStack.ai · OA
- Maximum Redundancy After One Segment FlipBloomberg LP · OABloomberg LP interview questions
- Substrings Without a Target SubsequencePhonePe · OAPhonePe interview questions
- Minimum Edit-Distance String for Each QueryTarget · OA
- Longest Subsequence That Is a SubstringWells Fargo · OAWells Fargo interview questions
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley Apprenticeship and Tech Interviews: 6 Experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)