String Traversal (single pass, running state)

Traversal visits each position in order—usually left to right with an index or for ch in s. It underpins search, hashing running aggregates, and building auxiliary arrays parallel to the string.

Why this shows up in the real world

Syntax highlighters traverse tokens sequentially. Stream checksums update rolling state per byte or char.

Core idea (explained for students)

Index loop: for i in range(len(s)): gives neighbors via s[i-1] guarded. Combined traversal: for i,(a,b) in enumerate(zip(s,t)): stops at shorter length.

Try this in Python

def prefix_balance(s: str) -> list[int]:
    bal, out = 0, []
    for c in s:
        bal += 1 if c == "(" else -1 if c == ")" else 0
        out.append(bal)
    return out


print(prefix_balance("(()"))

Common mistakes

• O(n²) hidden when each step does another full scan—amortize work.
• Using range(len(s)) when you only need chars—prefer direct iteration.

Key takeaways

• Single-pass algorithms are the default goal for long inputs.
• Keep a small struct of running state instead of rescanning prefixes.