Core Problem-Solving Patterns & String DP

Frequency Tables, Alphabet Compression, and Prefix Counts

Use a fixed-size frequency array when the alphabet is small and known, such as lowercase English letters or bytes. Map each symbol to an integer index and update counts in constant time. For arbitrary Unicode symbols or sparse alphabets, use a hash map so storage grows only with the number of distinct symbols encountered.

Alphabet compression combines these approaches: sort or otherwise enumerate the distinct symbols, assign each a dense identifier in $[0,\sigma-1]$, and then use compact arrays indexed by those identifiers. When many substring-frequency queries must be answered, precompute a prefix-count matrix where $P[i][c]$ counts occurrences of symbol $c$ in $S[0 \dots i-1]$. The frequency of $c$ in the half-open range $S[l \dots r)$ is then $P[r][c]-P[l][c]$.

Two Pointers and Sliding Windows

A two-pointer algorithm maintains an interval $S[L\dots R)$ and updates its summary as either boundary moves. It is useful when the problem admits a monotone decision: after extending the right boundary, repeatedly moving the left boundary must be sufficient to restore feasibility or minimize the current feasible interval.

A fixed-size window has a predetermined length $k$. Add $S[R]$, remove $S[R-k]$, and inspect the updated summary. Anagram search uses this pattern with a frequency-difference array: a window is an anagram when every difference is zero. Tracking the number of nonzero entries avoids comparing all $\sigma$ counters at every position.

A variable-size window expands until a condition becomes satisfied or violated, then contracts while the relevant invariant permits it:

• For the longest substring with at most $k$ distinct symbols, advance $R$, then move $L$ while the distinct count exceeds $k$.
• For a minimum covering substring, expand until every required multiplicity is satisfied, then contract while coverage remains valid.
• For a longest substring with replacement budget $k$, maintain the window length and the maximum symbol frequency.
• For additive constraints such as “sum at most $k$,” the usual monotone window generally requires nonnegative contributions; negative values can invalidate the method.

The window summary must encode multiplicity, not merely membership. Covering the target "AABC" requires two copies of A, so a set of symbols is insufficient.

Subsequence Dynamic Programming

Prefix DP is useful when a decision depends on progressively longer prefixes of two strings. For strings $A$ and $B$, define $\operatorname{LCS}[i][j]$ as the length of a longest common subsequence of $A[0 \dots i)$ and $B[0 \dots j)$. The base row and column are zero. If $A[i-1]=B[j-1]$, the matching symbol extends an optimal solution for the preceding prefixes; otherwise, discard one final symbol and take the better remaining state:

$$ \operatorname{LCS}[i][j]= \begin{cases} 1+\operatorname{LCS}[i-1][j-1], & A[i-1]=B[j-1],\\ \max(\operatorname{LCS}[i-1][j],\operatorname{LCS}[i][j-1]), & A[i-1]\ne B[j-1]. \end{cases} $$

A shortest common supersequence follows from the same prefix structure: matching final symbols are emitted once, while unequal symbols require choosing which prefix to shorten. Its optimal length is $|A|+|B|-\operatorname{LCS}(A,B)$.

For distinct-subsequence counting, let $D[i][j]$ count the ways the first $j$ symbols of target $T$ can be formed from the first $i$ symbols of source $S$. Every state may skip $S[i-1]$; when $S[i-1]=T[j-1]$, it may also use that occurrence:

$$ D[i][j]=D[i-1][j]+[S[i-1]=T[j-1]]D[i-1][j-1]. $$

The empty target has one realization, so $D[i][0]=1$, while a non-empty target cannot be formed from an empty source. For interleaving, state $(i,j)$ means that $A[0 \dots i)$ and $B[0 \dots j)$ form the first $i+j$ symbols of a third string; transitions consume the next matching symbol from either source.

Segmentation and Interval DP

Prefix DP partitions a string at boundaries. In Word Break, define reachable[i] to mean that $S[0\dots i)$ can be segmented into dictionary words:

$$ \operatorname{reachable}[i] = \bigvee_{0\leq j\lt i} \left( \operatorname{reachable}[j] \land S[j\dots i)\in D \right), $$

with $\operatorname{reachable}[0]=\mathrm{true}$. A parent array storing one successful boundary $j$ reconstructs a segmentation. Traversing a trie from each reachable boundary avoids constructing and hashing every possible candidate substring.

Interval DP uses states indexed by both ends of a substring. For the minimum number of insertions needed to make $S[i\dots j]$ a palindrome, define

$$ E[i][j] = \begin{cases} 0, & i\geq j,\\ E[i+1][j-1], & S[i]=S[j],\\ 1+\min(E[i+1][j],E[i][j-1]), & S[i]\neq S[j]. \end{cases} $$

Evaluate states by increasing interval length so that every shorter dependency has already been computed.

For palindrome partitioning, first precompute pal[i][j], indicating whether $S[i\dots j]$ is a palindrome. Then let pieces[i] be the minimum number of palindromic pieces covering $S[0\dots i)$. Initialize pieces[0] = 0; whenever $S[j\dots i)$ is palindromic, update from pieces[j] + 1. For a non-empty string, the minimum number of cuts is pieces[N] - 1.

flowchart TD
Empty["Boundary 0: reachable"]
PrefixJ["Reachable prefix ending at j"]
Word["Dictionary word S[j..i)"]
PrefixI["Reachable prefix ending at i"]
Inner["Shorter interval state"]
Pal["Palindrome state pal[i][j]"]
Partition["Best partition ending at i"]

```
Empty --> PrefixJ
PrefixJ --> PrefixI
Word --> PrefixI
Inner --> Pal
Pal --> Partition
PrefixJ --> Partition
```

Prefix states naturally use boundaries from $0$ through $N$. Interval states must explicitly state whether endpoints are inclusive or half-open; mixing those conventions is a common source of incorrect base cases and off-by-one errors.

Space Optimization, Reconstruction, and Testing

When a two-dimensional recurrence depends only on the preceding row and the current row, retain two rows instead of the full table. This reduces LCS length computation from $O(nm)$ space to $O(\min(n,m))$ while preserving its $O(nm)$ running time. A one-row implementation is also possible when cells are updated in an order that preserves every dependency.

Reconstruction requires more information. A full LCS table permits backtracking from $(n,m)$: matching symbols move diagonally and enter the answer, while unequal symbols move toward a neighboring state with the same optimal value. Parent pointers encode the same decisions explicitly. Hirschberg’s algorithm recovers an LCS using linear auxiliary space by combining forward and backward DP rows with divide and conquer.

Tests should cover empty strings, identical strings, disjoint alphabets, repeated symbols, ties with multiple valid witnesses, and highly unequal lengths. In Python, iteration operates on Unicode code points rather than user-perceived grapheme clusters; normalize text and segment graphemes explicitly when the application defines a “character” as a visible symbol.

def lcs_length_rolling(a: str, b: str) -> int:
    """Return the LCS length using O(min(len(a), len(b))) space."""
    if len(a) < len(b):
        a, b = b, a

    previous = [0] * (len(b) + 1)

    for char_a in a:
        current = [0] * (len(b) + 1)
        for j, char_b in enumerate(b, start=1):
            if char_a == char_b:
                current[j] = previous[j - 1] + 1
            else:
                current[j] = max(previous[j], current[j - 1])
        previous = current

    return previous[-1]


def lcs_reconstruct(a: str, b: str) -> str:
    """Return one longest common subsequence using a full DP table."""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

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

    result = []
    i, j = n, m

    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            result.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    result.reverse()
    return "".join(result)


def is_subsequence(candidate: str, text: str) -> bool:
    """Return whether candidate occurs as a subsequence of text."""
    index = 0

    for symbol in text:
        if index < len(candidate) and candidate[index] == symbol:
            index += 1

    return index == len(candidate)


if __name__ == "__main__":
    cases = [
        ("", ""),
        ("abc", ""),
        ("abc", "abc"),
        ("abc", "xyz"),
        ("banana", "atana"),
        ("A😀BC", "😀BD"),
    ]

    for left, right in cases:
        witness = lcs_reconstruct(left, right)
        expected_length = lcs_length_rolling(left, right)

        assert len(witness) == expected_length
        assert is_subsequence(witness, left)
        assert is_subsequence(witness, right)

        print(
            f"{left!r}, {right!r}: "
            f"length={expected_length}, witness={witness!r}"
        )