DSA Is a Subsequence

The problem

A subsequence is a string formed from another string by deleting some characters without reordering the rest. The pattern is the short string. The text is the long string it may hide inside.

The answer is True or False. The answer is True when every pattern letter appears in the text, in the same order, not necessarily side by side. The answer is False otherwise.

cases = [
    ("ace", "abcde", True),
    ("aec", "abcde", False),
    ("abc", "ahbgdc", True),
    ("axc", "ahbgdc", False),
]
for pattern, text, expected in cases:
    print("pattern", repr(pattern), "text", repr(text), "answer:", expected)

Read one row at a time. The letters a, c and e appear in order inside abcde, so the first row answers True. The letters a, e and c all appear in abcde too, but e comes after c there, so the second row answers False.

Intuition: checking that the letters exist

The first idea checks existence. Each pattern letter gets looked up in the text. Every letter found feels like progress.

Existence is not enough. The check never asks where a letter sits. Letters in the wrong order pass it anyway.

text = "abcde"
pattern = "aec"
present = True
for ch in pattern:
    if ch not in text:
        present = False
print("every letter exists:", present)
print("correct answer: False, because e comes after c in the text")

The printed True is the trap. Membership tests throw away position. Order is the whole question here, so the method has to track position while it checks.

Brute force: list every subsequence

A subsequence comes from choosing which text characters to keep. Each character is kept or deleted. A text of length n therefore has 2 to the power n subsequences.

The brute force lists them all. It builds every keep-or-delete choice as a string, and compares each string with the pattern. The method is plainly correct and plainly expensive.

text = "ahbgdc"
pattern = "abc"
subsequences = [""]
for ch in text:
    grown = []
    for s in subsequences:
        grown.append(s + ch)
    subsequences = subsequences + grown
tried = len(subsequences)
found = pattern in subsequences
print("subsequences tried:", tried)
print("pattern found:", found)

Six letters already force 64 tries. Each added letter doubles the count. A text of 30 letters would force over a billion tries, most of them for strings nobody asked about.

The optimal solution: one walk, two pointers

One pointer walking the text once, crossing off pattern letters in order, settles the question in a single pass. That one sentence is the whole method.

The pattern pointer p counts how many pattern letters have matched so far. A text character equal to pattern[p] advances p. Any other character changes nothing. Reaching the end of the pattern means every letter matched in order.

def is_subsequence(pattern, text):
    p = 0
    for ch in text:
        if p < len(pattern) and ch == pattern[p]:
            p += 1
    return p == len(pattern)

cases = [
    ("ace", "abcde", True),
    ("aec", "abcde", False),
    ("abc", "ahbgdc", True),
    ("axc", "ahbgdc", False),
]
for pattern, text, expected in cases:
    result = is_subsequence(pattern, text)
    print("pattern", repr(pattern), "text", repr(text), "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The failing rows fail for the right reason. Their pattern pointer stalls before the end of the pattern.

Walkthrough: pattern abc inside ahbgdc

The text is ahbgdc. The pattern is abc. The state after each character is one number, the count of matched letters, plus the indices where matches landed.

pattern = "abc"
text = "ahbgdc"
p = 0
path = []
for i, ch in enumerate(text):
    if p < len(pattern) and ch == pattern[p]:
        path.append(i)
        p += 1
    print("after index", i, "char", repr(ch), "- matched:", p, "at", path)
print("verdict:", p == len(pattern))

The letter h changes nothing. The letter g changes nothing. The three matches land at indices 0, 2 and 5, in increasing order, which is exactly what a subsequence needs.

Complexity

The two-pointer walk reads each text character once, so its time is O(len(text)). The brute force builds 2 to the power n strings for a text of length n, so its time grows exponentially.

The walk stores two counters and, in the walkthrough version, one index per match, so its extra space is O(1) besides any match list the caller asks it to keep.

def walk_steps(pattern, text):
    p = 0
    steps = 0
    for ch in text:
        steps += 1
        if p < len(pattern) and ch == pattern[p]:
            p += 1
    return steps

for n in [5, 10, 20]:
    text = "x" * n
    print("text length", n, "- walk steps:", walk_steps("a", text), " brute force tries:", 2 ** n)

Counts beat clocks here. The walk count grows by one per added letter. The brute-force count doubles per added letter. The gap is visible at length 20 already.

Edge cases and pitfalls

An empty pattern is a subsequence of every text. Zero letters need matching, so the count starts already complete. An empty text matches only the empty pattern.

A pattern longer than the text always fails. The text runs out before the pointer can finish. Repeated letters are the quieter trap, because each pattern letter needs its own separate text letter.

def is_subsequence(pattern, text):
    p = 0
    for ch in text:
        if p < len(pattern) and ch == pattern[p]:
            p += 1
    return p == len(pattern)

print("empty pattern:", is_subsequence("", "abc"))
print("empty text:", is_subsequence("a", ""))
print("both empty:", is_subsequence("", ""))
print("pattern longer than text:", is_subsequence("abcd", "abc"))
print("repeated letter, one copy in text:", is_subsequence("aa", "ba"))
print("repeated letter, two copies in text:", is_subsequence("aa", "aba"))

The repeated-letter rows show why the pointer must advance past a matched letter. One a in the text can satisfy only one a in the pattern.