0

Longest subsequence of one string that is a substring of another

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Longest subsequence of one string that is a substring of another

Companies: Microsoft

Difficulty: Medium

Problem statement

Given two strings x and y, return the length of the longest string t such that:

  • t is a subsequence of x: its characters appear in x in the same order, but not necessarily next to each other.
  • t is a substring of y: it appears in y as one contiguous block.

If no non-empty t exists, return 0.

def longest_subseq_substring(x: str, y: str) -> int: ...

Constraints

  • 0 <= len(x), len(y) <= 1000
  • Strings contain lowercase English letters.

Example 1

x = "sunday", y = "saturday"  ->  3

"day" is contiguous in y and appears in order in x (d, a, y). No longer substring of y works: "rday" needs an r, and x has none.

Example 2

x = "axbxcx", y = "zabcz"  ->  3

"abc" skips the x characters in x but is contiguous in y. Plain longest common subsequence is not the same problem: for x = "ab", y = "axb" it gives 2, but the answer here is 1, because "ab" is not contiguous in y.

Be ready to return the matching string itself, and to discuss how the solution changes if x is fixed and many different y strings arrive.

Approach

The answer is a string t with two properties: t is a subsequence of x (characters in order, gaps allowed) and a substring of y (contiguous). Contiguity in y is the key detail. Plain LCS lets both sides skip characters, so it overcounts here.

Brute force. List every substring of y (O(n²) of them) and test each one with a two-pointer subsequence check against x (O(m)). That is O(n²·m). Say it out loud, then improve it.

Observation that removes one factor. Fix a start index s in y. If y[s:e] is a subsequence of x, then every shorter prefix y[s:e'] is one too. So for each start you only need the longest prefix of y[s:] that is a subsequence of x. Greedy matching finds it: walk x once and advance in y whenever the characters match. Greedy is optimal for subsequence tests, because taking the earliest match in x never leaves fewer characters for later. This gives O(n·m) with O(1) extra space.

DP formulation (the one most interviewers expect, since this is an LCS variant).

Let dp[i][j] be the length of the longest string that is a subsequence of x[:i] and a substring of y that ends exactly at y[j-1].

  • If x[i-1] == y[j-1]: dp[i][j] = dp[i-1][j-1] + 1. Use this x character as the end of the match, and extend the match that ended at y[j-2].
  • Otherwise: dp[i][j] = dp[i-1][j]. Skip x[i-1]. Skipping is allowed in x because x only needs a subsequence.
  • Base: row 0 and column 0 are 0.
  • Answer: max(dp[m][j]) over all j.

Compare this with LCS. LCS has max(dp[i-1][j], dp[i][j-1]) in the mismatch case. Here there is no dp[i][j-1] term, because skipping a y character would break contiguity. The "ends exactly at j" anchor is what makes the substring side contiguous. This is the same trick as longest common substring.

Why taking the match is always safe. On a match, dp[i-1][j-1] + 1 >= dp[i-1][j], so the max of the two options is the match. A match ending at j that uses k characters of x[:i-1] can be shortened by its last character to give a match ending at j-1 of length k-1, so dp[i-1][j-1] >= dp[i-1][j] - 1.

Space. Row i reads only row i-1. Keep one array and update j from right to left, so dp[j-1] still holds the old row when dp[j] reads it.

Invariants.

  • After processing x[:i], dp[j] is the best match of x[:i] against substrings of y ending at y[j-1].
  • dp[j] <= min(i, j) at all times.

Code

from bisect import bisect_right
from collections import defaultdict


def longest_subseq_substring(x: str, y: str) -> int:
    """Length of the longest subsequence of x that is a substring of y.

    dp[j] = best length of a match whose substring of y ends exactly at y[j-1],
    using the prefix of x processed so far. One row, updated right to left.
    """
    n = len(y)
    dp = [0] * (n + 1)
    for ch in x:
        for j in range(n, 0, -1):  # right to left: dp[j-1] is still the previous row
            if y[j - 1] == ch:
                dp[j] = dp[j - 1] + 1
            # mismatch: dp[j] stays (skip ch in x)
    return max(dp)


def longest_subseq_substring_str(x: str, y: str) -> str:
    """Return one optimal string, not just its length.

    For each start s in y, greedily match y[s:] against x; the longest
    greedy prefix is the best match starting at s. O(len(x) * len(y)).
    """
    best_start, best_len = 0, 0
    for s in range(len(y)):
        if len(y) - s <= best_len:  # cannot beat the current best
            break
        k = s
        for ch in x:
            if k < len(y) and y[k] == ch:
                k += 1
        if k - s > best_len:
            best_start, best_len = s, k - s
    return y[best_start:best_start + best_len]


class SubseqIndex:
    """Preprocess x once to answer many y queries quickly.

    Greedy matching with binary search over each character's positions in x:
    each matched character costs O(log m) instead of a scan of x.
    """

    def __init__(self, x: str) -> None:
        self.pos: dict[str, list[int]] = defaultdict(list)
        for i, ch in enumerate(x):
            self.pos[ch].append(i)

    def _longest_from(self, y: str, s: int) -> int:
        i = -1  # last used index in x
        k = s
        while k < len(y):
            lst = self.pos.get(y[k])
            if not lst:
                break
            p = bisect_right(lst, i)
            if p == len(lst):
                break
            i = lst[p]
            k += 1
        return k - s

    def query(self, y: str) -> int:
        best = 0
        for s in range(len(y)):
            if len(y) - s <= best:
                break
            best = max(best, self._longest_from(y, s))
        return best


def brute_force(x: str, y: str) -> int:
    def is_subseq(t: str) -> bool:
        it = iter(x)
        return all(c in it for c in t)

    best = 0
    for a in range(len(y)):
        for b in range(a + 1, len(y) + 1):
            if b - a > best and is_subseq(y[a:b]):
                best = b - a
    return best


if __name__ == "__main__":
    import random

    assert longest_subseq_substring("sunday", "saturday") == 3        # "day"
    assert longest_subseq_substring_str("sunday", "saturday") == "day"
    assert longest_subseq_substring("kitten", "sitting") == 3         # "itt"
    assert longest_subseq_substring("abc", "xyz") == 0
    assert longest_subseq_substring("", "abc") == 0
    assert longest_subseq_substring("abc", "") == 0
    assert longest_subseq_substring("aaaa", "aa") == 2
    assert longest_subseq_substring("ab", "aaaa") == 1
    assert longest_subseq_substring("axbxcx", "zabcz") == 3            # "abc"
    assert longest_subseq_substring("cba", "abc") == 1
    for _ in range(2000):
        a = "".join(random.choice("abc") for _ in range(random.randint(0, 8)))
        b = "".join(random.choice("abc") for _ in range(random.randint(0, 8)))
        expected = brute_force(a, b)
        assert longest_subseq_substring(a, b) == expected
        assert len(longest_subseq_substring_str(a, b)) == expected
        assert SubseqIndex(a).query(b) == expected
    print("ok")

Complexity

With m = len(x) and n = len(y):

  • longest_subseq_substring (DP): O(m·n) time, O(n) space (one row). The full 2D table would be O(m·n) space.
  • longest_subseq_substring_str (greedy per start): O(m·n) time in the worst case, O(1) extra space besides the output. The early break skips starts that cannot beat the current best.
  • SubseqIndex: O(m) to build, O(m) space. A query costs O(n·L·log m), where L is the answer length, because each start matches at most L + 1 characters. This wins when x is long and the answer is short.
  • brute_force: O(n²·m), for testing only.

Test cases

  • x = "sunday", y = "saturday" → 3 ("day").
  • x = "kitten", y = "sitting" → 3 ("itt"; "itti" fails because x has no i after the tt).
  • x = "axbxcx", y = "zabcz" → 3 ("abc" skips the x characters in x, but is contiguous in y).
  • x = "cba", y = "abc" → 1 (order matters; any single character works).
  • x = "abc", y = "xyz" → 0 (no shared character).
  • x = "", y = "abc" → 0; x = "abc", y = "" → 0.
  • x = "aaaa", y = "aa" → 2 (bounded by len(y)).
  • x = "ab", y = "aaaa" → 1 (bounded by how many as x has; "aa" is not a subsequence of "ab").
  • x == y → len(x).
  • Randomized check against brute_force on short strings over a small alphabet.

Follow-ups

  1. Return the string, not the length. Track the j where dp[m][j] is largest. The match is y[j - L : j], because the matched substring of y is contiguous and ends at j - 1. You do not need to backtrack through x at all. The greedy-per-start version returns it directly.
  2. Swap the roles: a substring of x that is a subsequence of y. Call the same function with arguments swapped. Make sure the candidate states which string is which before coding. Mixing them up is the most common bug here.
  3. Many y queries against one long x (or the reverse). Preprocess x into per-character position lists (or a next[i][c] table, O(m·σ)). Then greedy matching jumps in O(log m) or O(1) per character, as in SubseqIndex. Since every substring of a valid match is also valid, a two-pointer window over y also works if you can test "is y[a:b] a subsequence of x" quickly. The jump table makes that test O(b − a).
  4. Count the distinct optimal strings, or list all of them. Collect every j with dp[m][j] == L and deduplicate y[j-L:j] with a set (or with rolling hashes for long inputs).
  5. Both sides contiguous, or both sides subsequences. Both contiguous is longest common substring: dp[i][j] = dp[i-1][j-1] + 1 on a match, else 0. Both subsequences is LCS: the mismatch case takes max(dp[i-1][j], dp[i][j-1]). A good candidate can show that only the mismatch rule changes between the three problems.

Interviewer expectations

Mid-level (L4)

  • Restates which string needs a subsequence and which needs a substring, and gives a small example where plain LCS gives the wrong answer.
  • Reaches a correct O(m·n) DP with clear state and base cases, possibly as a full 2D table.
  • Handles empty strings and the no-match case (0), and traces one example by hand.

Senior (L5)

  • Defines the state as "substring of y ending exactly at j" and explains why the mismatch case drops the dp[i][j-1] term.
  • Reduces space to one row and gets the update direction right (right to left), or explains the two-row alternative.
  • Returns the actual string from the end index, and tests with a brute-force cross-check or targeted edge cases.

Staff (L6+)

  • Notices that substrings of a valid match are valid, and uses it to offer the greedy-per-start method and a pruned search.
  • Handles the multi-query or very long x case with a next-occurrence table or position lists, and states the trade-offs (σ·m memory against log factors).
  • Places this problem among LCS and longest common substring, and shows that only the mismatch rule differs, so the solution is easy to adapt to the next part.

Sign in to comment, vote or remix.