Brute-force Algorithm (Longest Common Subsequence)

Definition

Brute-force Algorithm (Longest Common Subsequence)

Given two strings $S$ and $T$, the brute-force algorithm for the longest common subsequence problem enumerates every choice of positions in $S$, tests whether the resulting subsequence also occurs in $T$, and returns the greatest accepted length:

$$\max \{|A|:A\text{ is a subsequence of both }S\text{ and }T\}.$$

There are $2^{|S|}$ choices of positions: each position is either retained or omitted. Different choices can produce the same string when letters repeat.

Pseudocode

lcs_bruteforce(S, T):
    if |S| > |T|:
        swap(S, T)
    best := 0
    for each subset I of {0, ..., |S|-1}:
        A := letters S[i] for i in I, in increasing index order
        if is_subsequence(A, T):
            best := max(best, |A|)
    return best
 
is_subsequence(A, T):
    next := 0
    for each letter c in T:
        if next < |A| and A[next] == c:
            next := next + 1
    return next == |A|

The subsequence test matches each letter of $A$ at its earliest available position in $T$. Choosing an earlier match leaves at least as much of $T$ available for the remaining letters.

Correctness

Exact LCS Length

The algorithm returns the length of a longest common subsequence of $S$ and $T$.

Proof

After each iteration, best is the greatest length among the common subsequences examined so far.

No overestimate: every accepted string is a subsequence of $S$ by construction and of $T$ by the test. Thus best cannot exceed the optimum.

No underestimate: every common subsequence is realised by some choice of positions in $S$. In particular, the enumeration reaches a longest one and accepts it. Thus the final best is at least the optimum.

Together, these bounds give equality. If no non-empty common subsequence exists, the empty subsequence supplies the correct answer $0$.

Complexity

After swapping inputs if necessary, assume $|S|\le |T|$. Constructing each candidate costs $O(|S|)$ and checking it costs $O(|T|+1)$, including empty inputs. Therefore,

$$\underset{\text{position subsets}}{\underbrace{2^{|S|}}}\cdot \underset{\text{construct and test}}{\underbrace{O(|S|+|T|+1)}}=O(2^{|S|}(|T|+1)).$$

For non-empty $T$, this is $O(2^{|S|}|T|)$ time. Generating one candidate at a time uses $O(|S|+1)$ auxiliary space; storing all candidates is unnecessary.

Examples

Enumerating subsequences of abc

Let $S=\text{abc}$ and $T=\text{ac}$. Without swapping the inputs, the eight candidates are

$$\epsilon ,a,b,c,ab,ac,bc,abc.$$

Only $\epsilon ,a,c,ac$ are subsequences of $T$. Hence the answer is $|\text{ac}|=2$. Swapping the inputs reduces the enumeration to the four subsequences of $\text{ac}$ and gives the same answer.