Knowing What to Track

Pick the few numbers that let you answer the question at each step, and update them in O(1) as you scan: letter counts, a matched counter, a balance, an XOR.

Overview

Many array and string problems have a slow solution that looks at every window or every pair, and a fast one that scans the input once. The difference between them is almost always the same: the fast solution carries a small amount of state and updates it in O(1) at each step, instead of recomputing something from scratch.

Knowing what to track is the habit of asking, before you code: what do I need to know at this position to answer the question, and can I keep that up to date as I move? The state is usually one of a handful of things.

How often each value appears — A count per value (hash map, or an array of 26 for lowercase letters) — First unique character, Valid Sudoku
Whether two collections have the same counts — The counts of a moving window, plus a matched counter — Find All Anagrams, Permutation in String
Whether a window covers a required set — The counts, plus how many required values are satisfied — Minimum Window Substring
Opens and closes staying in step — One balance counter — Valid parentheses, minimum adds to make valid
Values that come in pairs — A running XOR — Single Number
Which items are 'the same' under rearranging — A signature used as a hash key — Group Anagrams

Counting

A frequency map turns 'is this value repeated?' from a comparison of pairs into a lookup. For first unique character, one pass counts the letters and a second pass returns the first letter whose count is 1.

Count — 3 — 1 — 1 — 1

Scanning the word again, 's' has count 3, so it is skipped, and 't' is the first letter with count 1. Two passes over n letters is O(n) time. The map has at most 26 keys for lowercase English letters, so the space is O(1) for that alphabet, or O(k) for an alphabet of size k.

In Python, collections.Counter is the usual tool: reading a missing key returns 0 instead of raising, so you never test for membership before you count. When the problem promises lowercase English letters, a list of 26 integers indexed by ord(ch) - ord('a') does the same job with no hashing.

Counts in a moving window

Find All Anagrams asks for every position where a window of s, exactly as long as p, has the same letter counts as p. Rebuilding the window's counts at every position costs O(k) per window for a pattern of length k. Instead, keep one count array for the window: when the window slides one step, add the letter that enters on the right and remove the letter that leaves on the left. Both are O(1).

Here is the trace on s = 'abcbac', p = 'abc'. The window is three letters long, so the first check happens at r = 2.

0 — a — a — a:1 — too short
1 — b — ab — a:1 b:1 — too short
2 — c — abc — a:1 b:1 c:1 — yes, start 0
3 — b — a — bcb — b:2 c:1 — no
4 — a — b — cba — a:1 b:1 c:1 — yes, start 2
5 — c — c — bac — a:1 b:1 c:1 — yes, start 3

The answer is [0, 2, 3]. Permutation in String is the same scan with a different return value: true as soon as one window matches.

The matched counter

The 'do the counts match?' step still compares 26 numbers per window, which is O(26 n) for the whole string. That is acceptable, but the O(n) version is a common follow-up, and the trick is worth knowing because it reappears in the variable-window problems.

Keep one more integer, matched: the number of letters, out of all 26, whose window count equals the count needed by p. Letters that are not in p have a needed count of 0, so they count as matched while they stay out of the window. The window is an anagram exactly when matched == 26.

Every time a count changes, only that one letter can move in or out of the matched set, so the update is O(1).

Count changes — If count[x] == need[x], matched drops by 1 — If count[x] == need[x] now, matched rises by 1

The same trace with the counter. Before the scan, 23 letters (every letter except a, b, c) already have count 0 == need 0, so matched starts at 23.

0 — a — 24
1 — b — 25
2 — c — 26 — yes
3 — b — a — 24 — no
4 — a — b — 26 — yes
5 — c — c — 26 — yes

At r = 3 two things go wrong at once: b's count becomes 2 (one more than needed) and a's count becomes 0 (one less), so matched falls by 2. At r = 5 a c enters and a c leaves, so the counts end where they started and matched is back at 26 (it dips to 25 between the two updates).

A window that grows and shrinks

Minimum Window Substring asks for the shortest substring of s that contains every character of t, with repeats. The window is no longer a fixed size, so the pattern becomes: extend the right end until the window is valid, then pull the left end in while it stays valid, recording the shortest valid window seen.

What to track: the window's counts, the needed counts, and formed, the number of distinct characters of t whose window count has reached the needed count. The window is valid when formed equals the number of distinct characters in t. As with the matched counter, only the character just added or removed can change formed.

Trace on s = 'aaxbcab', t = 'abc'. Three distinct characters are needed.

0 — a — a — 1 — a
1 — a — aa — 1 — aa
2 — x — aax — 1 — aax
3 — b — aaxb — 2 — aaxb
4 — c — aaxbc — 3 — a, a — xbc — axbc
5 — a — xbca — 3 — x, b — ca — bca
6 — b — cab — 3 — c — ab — bca

At r = 4 the window becomes valid for the first time. Dropping the first 'a' keeps it valid (the window still has one 'a'), so the loop drops the second 'a' as well, which breaks validity and stops the shrinking. The answer is 'bca', length 3.

The usual follow-up is the O(m + n) bound, where m and n are the lengths of s and t. It holds because l and r each move only forward, so the two loops together do at most 2m steps, and each step is O(1) thanks to formed.

A balance

Bracket problems need even less: one integer. Add 1 for an opening bracket and subtract 1 for a closing one. The string is balanced when the counter never goes below 0 and ends at 0. A dip below 0 means a closing bracket arrived with nothing to close.

(()()) — 1, 2, 1, 2, 1, 0 — valid
())( — 1, 0, -1, 0 — invalid: went below 0
(() — 1, 2, 1 — invalid: ended above 0

For 'how many brackets must be added to make it valid', track two numbers: unmatched opens so far, and the number of closes that arrived with nothing to close. Each time the balance would go negative, count one needed open and reset. The answer is both counts added together: for '())' it is 1, for '(((' it is 3, for '))((' it is 4.

A balance works when there is one kind of bracket. With several kinds, the order matters too, and the state becomes a stack.

Pairs that cancel

XOR has two properties that make it a tracker: x ^ x == 0 and x ^ 0 == x, and the order does not matter. So if every value in an array appears exactly twice except one, the XOR of everything is that one value, with no map at all.

4 — 4
1 — 5
2 — 7
1 — 6
2 — 4

For two values that appear once, say a and b, the XOR of everything is a ^ b. Any bit set in it is a bit where a and b differ. Split the array by that bit and XOR each half separately: each half holds one of the two, and the pairs still cancel inside their half. On [1, 2, 1, 3, 2, 5] the total XOR is 6 (binary 110), the lowest set bit is 2, the values with that bit set are [2, 3, 2] with XOR 3, and the others are [1, 1, 5] with XOR 5.

A signature as a key

Group Anagrams asks for the words that are rearrangements of each other. The trick is to compute, for each word, a key that is the same for all its anagrams, and group by the key in a hash map.

Sorted letters — 'aet' — O(k log k)
Tuple of 26 counts — (1, 0, 0, 0, 1, 0, …, 1, …) — O(k + 26)

Both work. The count tuple avoids the sort and is the one to mention when asked for the fastest version; the sorted string is shorter to write.

Several trackers at once

Valid Sudoku needs a different set of 'seen digits' for each row, each column and each 3 x 3 box: 27 sets. A single pass over the 81 cells adds each filled digit to its three sets and answers false on the first repeat.

The one formula to remember is the box index for the cell in row r and column c: (r // 3) * 3 + c // 3. Rows 0 to 2 give the top three boxes, numbered 0, 1, 2 from left to right.

Rows 0 to 2 — box 0 — box 1 — box 2
Rows 3 to 5 — box 3 — box 4 — box 5
Rows 6 to 8 — box 6 — box 7 — box 8

What you will be able to do

Say, before coding, which quantity the answer depends on and how to update it in O(1) per step.
Slide a fixed window over a string with one add and one remove, and use a matched counter instead of comparing 26 counts.
Solve Minimum Window Substring with expand-then-shrink and explain why it is O(m + n).
Use a balance counter for one kind of bracket and a running XOR for values that pair off.
Choose a grouping key for anagrams and give the cost of each choice.

When to use it

Anagram or permutation questions on a window of fixed length (Find All Anagrams, Permutation in String)
Shortest window that covers a set of required characters (Minimum Window Substring)
Grouping items that are equal after rearranging (Group Anagrams)
Constraints on repeats across several groupings at once (Valid Sudoku)
Brackets of one kind: valid or not, and the fewest additions to make it valid
One or two values that break a pairing (Single Number and its two-value variant)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio