Substring Tracking (last index, sliding maps)

Substring tracking maintains state about where substrings occurred—last index map, active window counts, or automaton nodes while scanning. Sliding-window frequency maps are the classic companion pattern.

Why this shows up in the real world

Intrusion systems track recent suspicious command substrings. Editors maintain incremental match state for live search.

Core idea (explained for students)

last = {c: -1 for c in alphabet} updated as you scan; minimum of last positions defines window covering all required chars. For duplicates, use deques per char.

Try this in Python

def last_positions(s: str) -> dict[str, int]:
    last: dict[str, int] = {}
    for i, c in enumerate(s):
        last[c] = i
    return last


print(last_positions("abacabad"))

Common mistakes

• Stale indices after deletions from a window—decrement counts carefully.
• Off-by-one when shrinking window from the left.

Key takeaways

• Pair maps with monotonic queue ideas when you need min over a sliding set.
• Log window snapshots only at debug verbosity.