String Subsequence Problems

A subsequence is a sequence of characters from a string that maintains their relative order but doesn’t need to be contiguous. From “abcde”, the strings “ace”, “abd”, “abcde”, and “a” are all subsequences, but “aec” is not (the order is wrong).

Subsequence problems are everywhere in interviews. They test your understanding of two pointers, dynamic programming, and sometimes binary search. The good news: once you learn the patterns, the problems become very recognizable.

1. Is subsequence

The simplest problem (LeetCode 392): given strings s and t, check if s is a subsequence of t.

Two-pointer approach

Walk through t with one pointer and s with another. Advance the s pointer whenever we find a matching character:

def is_subsequence(s: str, t: str) -> bool:
    """Check if s is a subsequence of t. O(n) time, O(1) space."""
    if not s:
        return True

    s_idx = 0
    for char in t:
        if char == s[s_idx]:
            s_idx += 1
            if s_idx == len(s):
                return True

    return s_idx == len(s)

Time complexity: O(n) where n = len(t) — we scan t once. Space complexity: O(1).

Iterator-based Python one-liner

Python’s iterators make this elegantly concise:

def is_subsequence_pythonic(s: str, t: str) -> bool:
    """Pythonic subsequence check using iterators. O(n) time."""
    t_iter = iter(t)
    return all(c in t_iter for c in s)

This works because in on an iterator consumes elements until it finds a match (or exhausts the iterator). Each character of s picks up where the last one left off.

Follow-up: Many subsequences to check

LeetCode 392 has a follow-up: what if we have many strings s1, s2, ... to check against the same t? Scanning t from scratch each time is wasteful.

Pre-process t with binary search:

Build an index mapping each character to its sorted list of positions in t. For each character in s, binary search for the next valid position:

from collections import defaultdict
from bisect import bisect_left

def is_subsequence_binary_search(s: str, t: str) -> bool:
    """Subsequence check with binary search. O(m log n) per query after O(n) preprocessing."""
    # Preprocess: map each character to sorted list of indices
    char_indices = defaultdict(list)
    for i, c in enumerate(t):
        char_indices[c].append(i)

    # For each character in s, find the next valid position
    prev_pos = -1
    for c in s:
        if c not in char_indices:
            return False
        positions = char_indices[c]
        # Find first position > prev_pos
        idx = bisect_left(positions, prev_pos + 1)
        if idx == len(positions):
            return False  # No valid position found
        prev_pos = positions[idx]

    return True


class SubsequenceChecker:
    """Efficient checker for multiple subsequence queries against the same string."""

    def __init__(self, t: str):
        """Preprocess t in O(n) time."""
        self.char_indices = defaultdict(list)
        for i, c in enumerate(t):
            self.char_indices[c].append(i)

    def is_subsequence(self, s: str) -> bool:
        """Check one query in O(m log n) time."""
        prev_pos = -1
        for c in s:
            if c not in self.char_indices:
                return False
            positions = self.char_indices[c]
            idx = bisect_left(positions, prev_pos + 1)
            if idx == len(positions):
                return False
            prev_pos = positions[idx]
        return True

Preprocessing: O(n) time and space. Per query: O(m log n) where m = len(s).

DP approach for is_subsequence

We can also use DP to precompute a “next occurrence” table. For each position in t and each character, store where that character next appears:

def preprocess_subsequence(t: str):
    """Build next-occurrence table. O(26n) time and space."""
    n = len(t)
    # nxt[i][c] = next position of character c at or after position i
    nxt = [[n] * 26 for _ in range(n + 1)]

    for i in range(n - 1, -1, -1):
        for c in range(26):
            nxt[i][c] = nxt[i + 1][c]
        nxt[i][ord(t[i]) - ord('a')] = i

    return nxt


def is_subsequence_dp(s: str, t: str, nxt: list) -> bool:
    """Check subsequence using precomputed table. O(m) per query."""
    n = len(t)
    pos = 0
    for c in s:
        idx = ord(c) - ord('a')
        if pos >= n or nxt[pos][idx] >= n:
            return False
        pos = nxt[pos][idx] + 1
    return True

This makes each query O(m) — no binary search needed — at the cost of O(26n) preprocessing space.

2. Number of distinct subsequences

LeetCode 115: given strings s and t, count how many distinct subsequences of s equal t. For example, s = "rabbbit", t = "rabbit" returns 3 because there are three ways to choose the letters.

This is a classic DP problem.

The recurrence

Define dp[i][j] = number of ways to form t[0:j] from s[0:i].

• If s[i-1] == t[j-1]: we can either use this character (dp[i-1][j-1]) or skip it (dp[i-1][j]).
• If s[i-1] != t[j-1]: we must skip s[i-1], so dp[i][j] = dp[i-1][j].
• Base case: dp[i][0] = 1 for all i — the empty string is a subsequence of everything.

def num_distinct(s: str, t: str) -> int:
    """Count distinct subsequences of s that equal t. O(m*n) time and space."""
    m, n = len(s), len(t)

    # dp[i][j] = ways to form t[0:j] from s[0:i]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Empty string is a subsequence of any prefix
    for i in range(m + 1):
        dp[i][0] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i - 1][j]  # Skip s[i-1]
            if s[i - 1] == t[j - 1]:
                dp[i][j] += dp[i - 1][j - 1]  # Use s[i-1]

    return dp[m][n]

Time complexity: O(m * n). Space complexity: O(m * n), reducible to O(n) with a 1D array.

Space-optimized version

Since each row only depends on the previous row, we can use a 1D array. But we must iterate j in reverse to avoid overwriting values we still need:

def num_distinct_optimized(s: str, t: str) -> int:
    """Space-optimized distinct subsequences. O(m*n) time, O(n) space."""
    m, n = len(s), len(t)
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty string

    for i in range(1, m + 1):
        # Traverse right to left to avoid overwriting
        for j in range(n, 0, -1):
            if s[i - 1] == t[j - 1]:
                dp[j] += dp[j - 1]

    return dp[n]

3. Longest common subsequence (LCS)

LeetCode 1143: given two strings, find the length of their longest common subsequence. This is one of the most fundamental DP problems in computer science.

Standard DP solution

def longest_common_subsequence(text1: str, text2: str) -> int:
    """Find LCS length. O(m*n) time and space."""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

The recurrence explained:

• If the current characters match, extend the LCS by 1 from the diagonal.
• If they don’t match, take the better of excluding either character.

Reconstructing the actual LCS

The DP table tells us the length, but often we need the actual subsequence. Trace back from dp[m][n]:

def find_lcs(text1: str, text2: str) -> str:
    """Find the actual LCS string. O(m*n) time and space."""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Backtrack to find the LCS
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i - 1] == text2[j - 1]:
            lcs.append(text1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(lcs))

Space-optimized LCS length

If you only need the length, use two rows:

def lcs_space_optimized(text1: str, text2: str) -> int:
    """LCS length with O(min(m,n)) space."""
    # Make text2 the shorter string for space savings
    if len(text1) < len(text2):
        text1, text2 = text2, text1

    m, n = len(text1), len(text2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)

    return prev[n]

Space complexity: O(min(m, n)).

4. Shortest common supersequence

LeetCode 1092: given two strings, find the shortest string that has both as subsequences. For example, str1 = "abac", str2 = "cab" gives "cabac".

The key insight: the shortest common supersequence has length len(str1) + len(str2) - LCS_length. We need to interleave the characters, using the LCS as the shared backbone.

def shortest_common_supersequence(str1: str, str2: str) -> str:
    """Build shortest common supersequence using LCS. O(m*n) time and space."""
    m, n = len(str1), len(str2)

    # Step 1: Compute LCS DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Step 2: Backtrack to build the supersequence
    result = []
    i, j = m, n

    while i > 0 and j > 0:
        if str1[i - 1] == str2[j - 1]:
            # Common character — include once
            result.append(str1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            # str1[i-1] is not in LCS at this point — include it
            result.append(str1[i - 1])
            i -= 1
        else:
            # str2[j-1] is not in LCS at this point — include it
            result.append(str2[j - 1])
            j -= 1

    # Add remaining characters
    while i > 0:
        result.append(str1[i - 1])
        i -= 1
    while j > 0:
        result.append(str2[j - 1])
        j -= 1

    return ''.join(reversed(result))

Time complexity: O(m * n) for the DP table. Space complexity: O(m * n).

Why this works: We trace back through the LCS table. When characters match (part of the LCS), we include them once. When they don’t match, we include the character that wasn’t part of the LCS path. This guarantees both original strings are subsequences of the result.

5. Subsequence variants

Number of matching subsequences (LeetCode 792)

Given a string s and a list of words, count how many words are subsequences of s:

from collections import defaultdict
from bisect import bisect_left

def num_matching_subseq(s: str, words: list) -> int:
    """Count words that are subsequences of s. O(n + sum(len(word)) * log n)."""
    # Preprocess s
    char_indices = defaultdict(list)
    for i, c in enumerate(s):
        char_indices[c].append(i)

    count = 0
    for word in words:
        prev = -1
        found = True
        for c in word:
            if c not in char_indices:
                found = False
                break
            positions = char_indices[c]
            idx = bisect_left(positions, prev + 1)
            if idx == len(positions):
                found = False
                break
            prev = positions[idx]
        if found:
            count += 1

    return count

Delete operation for two strings (LeetCode 583)

Find the minimum number of deletions to make two strings equal. This reduces to LCS:

def min_distance(word1: str, word2: str) -> int:
    """Minimum deletions to make strings equal. O(m*n) time."""
    lcs_len = longest_common_subsequence(word1, word2)
    return len(word1) + len(word2) - 2 * lcs_len

The characters we keep are the LCS. Everything else gets deleted.

Interleaving string (LeetCode 97)

Check if s3 is formed by interleaving s1 and s2:

def is_interleave(s1: str, s2: str, s3: str) -> bool:
    """Check if s3 is an interleaving of s1 and s2. O(m*n) time and space."""
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False

    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for i in range(1, m + 1):
        dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

    for j in range(1, n + 1):
        dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (
                (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or
                (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
            )

    return dp[m][n]

Big-O summary

Problem	Time	Space
Is subsequence (two pointers)	O(n)	O(1)
Is subsequence (binary search, per query)	O(m log n)	O(n) preprocessing
Distinct subsequences	O(m * n)	O(n) optimized
Longest common subsequence	O(m * n)	O(m * n) or O(min(m,n))
Shortest common supersequence	O(m * n)	O(m * n)
Interleaving string	O(m * n)	O(m * n)

Practice problems

1. Is Subsequence (LeetCode 392) — Two pointers, then binary search follow-up
2. Distinct Subsequences (LeetCode 115) — 2D DP with space optimization
3. Longest Common Subsequence (LeetCode 1143) — Foundational DP
4. Shortest Common Supersequence (LeetCode 1092) — LCS + backtracking construction
5. Number of Matching Subsequences (LeetCode 792) — Binary search preprocessing
6. Delete Operation for Two Strings (LeetCode 583) — LCS reduction
7. Interleaving String (LeetCode 97) — 2D DP grid
8. Longest Increasing Subsequence (LeetCode 300) — Related pattern (see arrays section)
9. Edit Distance (LeetCode 72) — Close cousin of LCS

Key takeaways

• Two pointers solve the basic “is subsequence” check in O(n) time. This is a pattern you’ll use everywhere.
• Binary search preprocessing transforms repeated subsequence queries from O(n) each to O(m log n) each — a huge win when the target string is fixed.
• LCS is the foundation for many subsequence problems. Learn the recurrence cold: match extends diagonally, mismatch takes the max of skipping either character.
• Shortest common supersequence builds on LCS — the supersequence length is len(s1) + len(s2) - LCS. Reconstruct by tracing back through the DP table.
• Distinct subsequences uses a different recurrence: when characters match, you can use it or skip it. When they don’t match, you must skip.