Subsequence Matching in Go: The Two-Pointer Scan

Have you ever wondered how tools like fzf, VS Code's command palette, or fuzzy finders work under the hood? The core logic is often a subsequence match — and it's surprisingly simple to implement.

In this post, we'll break down a compact Go function called WdMatch that does exactly this.

---

The Full Function

func WdMatch() {
    if len(os.Args) != 3 {
        os.Stdout.Write([]byte("\n"))
        return
    }

    s1 := os.Args[1] // pattern  (needle)
    s2 := os.Args[2] // haystack (text)

    i := 0

    for j := 0; j < len(s2) && i < len(s1); j++ {
        if s1[i] == s2[j] {
            i++
        }
    }

    if i == len(s1) {
        os.Stdout.Write([]byte(s1 + "\n"))
    }
}

---

What Does It Do?

It checks whether every character of s1 (the pattern) appears in order inside s2 (the text) — not necessarily contiguous. If they do, it prints the pattern. Otherwise, it prints nothing.

This is called a subsequence check.

For example:

• "ace" is a subsequence of "abcde" ✅ — a, c, e all appear in order
• "aec" is not a subsequence of "abcde" ❌ — e comes after c in the text, breaking the order

---

Algorithm Walkthrough

Step 1 — Validate arguments

if len(os.Args) != 3 {
    os.Stdout.Write([]byte("\n"))
    return
}

The program expects exactly 3 arguments: the binary name + 2 strings. If that's not the case, it writes a bare newline and exits cleanly — no panic.

---

Step 2 — Assign the two strings

s1 := os.Args[1] // pattern
s2 := os.Args[2] // text
i := 0

s1 is what we're searching for. s2 is where we search. i tracks how far we've matched into the pattern.

---

Step 3 — The two-pointer loop

for j := 0; j < len(s2) && i < len(s1); j++ {
    if s1[i] == s2[j] {
        i++
    }
}

This is the core. Two pointers move through the strings:

• j always advances — it walks every character of s2
• i only advances when s1[i] == s2[j] — a match is found

The loop has a dual exit condition: it stops when s2 is exhausted OR when the full pattern has been matched (early exit).

---

Step 4 — Check for a complete match

if i == len(s1) {
    os.Stdout.Write([]byte(s1 + "\n"))
}

After the loop, if i reached the end of s1, every character was found in the right order. Pattern is printed. Otherwise — silence.

---

Dry Run Examples

✅ Match: "ace" in "abcde"

j	s2[j]	s1[i]	Match?	i after
0	a	a	✅	1
1	b	c	❌	1
2	c	c	✅	2
3	d	e	❌	2
4	e	e	✅	3

i == len("ace") == 3 → prints ace

---

❌ No Match: "aec" in "abcde"

j	s2[j]	s1[i]	Match?	i after
0	a	a	✅	1
1	b	e	❌	1
2	c	e	❌	1
3	d	e	❌	1
4	e	e	✅	2

Loop ends. i == 2, but len("aec") == 3 → nothing printed.

---

Complexity

Time	O(n) where n = len(s2)
Space	O(1) — no allocations inside the loop

Each character in s2 is visited at most once. Only two integer pointers are maintained.

---

Edge Cases

Scenario	Behaviour
Wrong arg count	Writes \n, returns immediately
Empty pattern ""	Always matches — i == 0 == len(s1) after loop
Empty text ""	Loop never runs; only empty pattern matches
Pattern longer than text	Loop exits before i reaches len(s1) — no match
Multi-byte Unicode	Byte indexing s1[i] breaks on chars like é. Use []rune instead

---

Running It

# match: prints "ace"
go run main.go ace abcde

# no match: prints nothing
go run main.go aec abcde

# wrong args: prints a bare newline
go run main.go ace

---

Refactored: Separate the Logic from the CLI

The original function mixes argument parsing with the matching logic. Splitting them makes the core algorithm independently testable:

// IsSubsequence returns true if every byte of pattern
// appears in text in the same order.
func IsSubsequence(pattern, text string) bool {
    i := 0
    for j := 0; j < len(text) && i < len(pattern); j++ {
        if pattern[i] == text[j] {
            i++
        }
    }
    return i == len(pattern)
}

func WdMatch() {
    if len(os.Args) != 3 {
        os.Stdout.Write([]byte("\n"))
        return
    }
    if IsSubsequence(os.Args[1], os.Args[2]) {
        os.Stdout.Write([]byte(os.Args[1] + "\n"))
    }
}

Now you can write unit tests directly against IsSubsequence without touching os.Args.

---

Unicode Support

The original uses byte indexing (s1[i], s2[j]), which works perfectly for ASCII but breaks on multi-byte Unicode characters like é, 中, or 🔥.

To support full Unicode, convert to rune slices:

func IsSubsequenceRune(pattern, text string) bool {
    p := []rune(pattern)
    t := []rune(text)
    i := 0
    for j := 0; j < len(t) && i < len(p); j++ {
        if p[i] == t[j] {
            i++
        }
    }
    return i == len(p)
}

Same logic — just operating on code points instead of bytes.

---

Wrapping Up

WdMatch is a clean, allocation-free implementation of subsequence matching in about 15 lines of Go. The two-pointer approach is the same pattern powering real-world fuzzy finders — linear in the length of the text, constant in space, and easy to reason about.

If you found this useful, the next step is applying it to a list of words and filtering only those that match a given pattern — which is exactly how command-palette search works.

---

Written with ❤️ in Go

If you enjoyed this, feel free to check out more of my work on GitHub
👉 keyadaniel56 — always building something new in Go and beyond.