Longest Common Subsequence
Updated
Problem statement
You are given two strings, text1 and text2.
A subsequence of a string is what is left after you delete zero or more of its characters and keep the rest in their original order. For example, "tin" is a subsequence of "string", but "nit" is not. A common subsequence of two strings is a string that is a subsequence of both of them.
Return the length of the longest common subsequence of text1 and text2. If the only common subsequence is the empty string, return 0.
Function
longestCommonSubsequence(text1: String, text2: String) → intExamples
Example 1
text1 = "mountain"text2 = "maintain"return = 6One longest common subsequence is "mntain". In "mountain" it skips the 'o' and the 'u', and in "maintain" it skips the first 'a' and the first 'i'. No common subsequence has 7 letters.
Example 2
text1 = "stone"text2 = "notes"return = 2Both strings use the same five letters, but in different orders. One longest common subsequence is "ne": in both strings the 'n' comes before the 'e'. No common subsequence has 3 letters.
Example 3
text1 = "day"text2 = "quiz"return = 0No letter appears in both strings, so the only common subsequence is the empty string, whose length is 0.
Constraints
1 <= text1.length, text2.length <= 1000text1andtext2contain only lowercase English letters.
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Longest Palindromic SubstringSiemens · PHONE SCREEN
- Query Words Within K PositionsPalantir · PHONE SCREENPalantir interview questions
- Edit DistanceDP World · PHONE SCREEN
- Longest Palindromic SubstringIBM · PHONE SCREENIBM interview questions
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Decode WaysThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Edit DistanceAstrotalk · PHONE SCREEN
- Longest Palindromic SubstringeBay · PHONE SCREENeBay interview questions
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Count Palindromic SubstringsThe Voleon Group · PHONE SCREEN
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
- Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)