Longest Common Subsequence
Updated
Problem statement
Given two strings text1 and text2, return the length of their longest common subsequence. If they have no common subsequence other than the empty one, return 0.
A subsequence of a string is what remains after deleting some characters (possibly none) without changing the order of the rest. For example, ace is a subsequence of abcde. A common subsequence is a subsequence of both strings.
Function
longestCommonSubsequence(text1: String, text2: String) → intExamples
Example 1
text1 = "kitten"text2 = "sitting"return = 4ittn is a subsequence of both: delete k and e from kitten, or delete s, the second i and g from sitting. No common subsequence has 5 letters, so the answer is 4.
Example 2
text1 = "abc"text2 = "xyz"return = 0The strings share no letter, so the only common subsequence is the empty one. The answer is 0.
Example 3
text1 = "abcba"text2 = "abacb"return = 4abcb is a subsequence of both: delete the last a of abcba, or the second a of abacb. The strings are not equal and each has 5 letters, so no common subsequence has 5 letters; the answer is 4.
Constraints
1 <= text1.length, text2.length <= 1000text1andtext2consist of lowercase English letters.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Maximum Bouquet ValueOracle · ONSITE INTERVIEWOracle interview questions
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Word BreakGoogle · ONSITE INTERVIEWGoogle 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
- Minimum Steps on a Circular Character DialNavan · ONSITE INTERVIEWNavan interview questions