Longest Subsequence That Is a Substring
Updated
Problem statement
You are given two strings x and y. Look for a string that meets both of these rules:
- It is a subsequence of
x. You can get it by deleting any number of letters fromx, or none, and keeping the rest in order. - It is a substring of
y. It has at least one letter, and its letters sit next to each other inywith no gaps.
Return the length of the longest string that meets both rules. If no letter of x appears in y, no such string exists, so return 0.
Function
longestSubsequence(x: String, y: String) → intExamples
Example 1
x = "abcd"y = "abdc"return = 3The string abd is a subsequence of x, by deleting c. It is also the first three letters of y. The only substring of y with 4 letters is abdc, and it is not a subsequence of x, because d comes before c in it but after c in x. So the answer is 3.
Example 2
x = "bcd"y = "abcd"return = 3All of x is a substring of y, starting at index 1. The match does not have to start at index 0.
Example 3
x = "apbqc"y = "abc"return = 3All of y is abc. You can get it from x by deleting p and q, so the letters may have gaps in x.
Example 4
x = "abc"y = "apbqc"return = 1The letters a, b, and c all appear in y in order, but with gaps, so abc is not a substring of y. Every substring of y with two or more letters contains p or q, and x has neither. So the answer is 1.
Example 5
x = "abc"y = "def"return = 0The two strings share no letter, so the answer is 0.
Constraints
1 <= x.length <= 20001 <= y.length <= 2000xandycontain only lowercase English letters.
More Expedia Online Assessment questions
- Balanced NumbersOA · Seen Aug 2026
- REST API: Discounted PriceOA · Seen Aug 2026
- Maximum Team SizeOA · Seen Mar 2026
- Per-Domain Request LimiterOA · Seen Oct 2025
- Count Equal-Frequency SubsequencesOA · Seen Mar 2025
- Count Increasing Stock PeriodsOA · Seen Mar 2025
- Get Minimum StepsOA · Seen Oct 2024
- Rank Songs by PopularityOA · Seen Oct 2024
- Calculate the SumOA · Seen Oct 2024
- Get Maximum EfficiencyOA · Seen Oct 2024
Similar questions at other companies
- Longest Subsequence which is a SubstringSalesforce · OASalesforce 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
- Longest Properly Closed Bracket RunAdobe · PHONE SCREENAdobe interview questions
- Indexed Proximity SearchStripe · PHONE SCREENStripe interview questions
- Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)