FastPrepLongest Subsequence That Is a Substring
Problems/Longest Subsequence That Is a Substring

Longest Subsequence That Is a Substring

Expedia logoExpedia● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks how long a string can be if it is a subsequence of x and also a substring of y. It gives one example, which is Example 1 here.

The report's text is cut off, so it gives no return type or limits, and it does not say what to return when nothing matches. Here, you return the length as an integer, and 0 when the strings share no letter. The limits, the lowercase letters, and the other examples are our choices, not from the report.

Our version is about 90% the same as the reported question.

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 from x, 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 in y with 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) → int

Examples

Example 1

x = "abcd"y = "abdc"return = 3

The 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 = 3

All 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 = 3

All 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 = 1

The 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 = 0

The two strings share no letter, so the answer is 0.

Constraints

  • 1 <= x.length <= 2000
  • 1 <= y.length <= 2000
  • x and y contain 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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int longestSubsequence(String x, String y) {
        // Write your code here.
    }
}
Checking account…