Is Subsequence

Is s a subsequence of t — can you get s by deleting characters from t without reordering what is left?

isSubsequence("abc", "ahbgdc")   // true
isSubsequence("axc", "ahbgdc")   // false

The idea

Walk t once. Keep a pointer into s. Every time the character under the t pointer is the one s currently wants, advance s. At the end, s is a subsequence if its pointer reached the end.

Neither pointer ever moves backwards, so this is one pass — $O(|t|)$ time, $O(1)$ space.

The solution, and the crash in it

func isSubsequence(s string, t string) bool {
    sRunes := []rune(s)
    tRunes := []rune(t)

    var index = 0

    for _, v := range tRunes {
        if index < len(s) && v == sRunes[index] {
            index++
        }
    }

    if index == len(sRunes) {
        return true
    }

    return false
}

This passes LeetCode, and it panics on non-ASCII input.

The tidied version

func isSubsequence(s string, t string) bool {
    sRunes, tRunes := []rune(s), []rune(t)
    index := 0

    for _, v := range tRunes {
        if index == len(sRunes) {
            break            // s is fully matched; the rest of t cannot matter
        }
        if v == sRunes[index] {
            index++
        }
    }

    return index == len(sRunes)
}

Two changes beyond the fix. The early break stops walking t once s is exhausted — same complexity, less work. And return index == len(sRunes) replaces if … { return true }; return false, which is the same expression written twice.

The follow-up is the interesting part

Suppose there are many incoming s — say a billion — and one fixed t. How would you change your code?

The single pass is $O(|t|)$ per query, so a billion queries means a billion walks over t. The fix is to preprocess t once:

// For each position in t and each letter, where is the next occurrence?
next := make([][26]int, len(t)+1)
for c := range next[len(t)] {
    next[len(t)][c] = len(t)          // sentinel: not found
}
for i := len(t) - 1; i >= 0; i-- {
    next[i] = next[i+1]
    next[i][t[i]-'a'] = i
}

Now each query jumps straight to the next useful position instead of scanning: $O(|s| \log \Sigma)$ — effectively $O(|s|)$ — after an $O(|t| \cdot \Sigma)$ build.

That trade shows up whenever one input is fixed and the other streams: pay once to build an index, then answer each query in time proportional to the query rather than the data.