String and Pattern

What is this?

These tricky string and grid problems aren't really about scanning substrings — each turns on noticing a derived quantity that makes the brute-force search vanish. The single insight might be the lengths of adjacent runs, one simple counter, a careful flag-based scan, or the offset between two sets of points. Once you summarize the input the right way, the answer is almost already there.

💡 Fun fact: For Count Binary Substrings, compressing a string like 00110 into run lengths [2,2,1] means each adjacent pair contributes exactly the smaller of the two runs — turning a substring-counting problem into a quick walk over a handful of numbers.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Some string and grid problems aren't about substrings at all — they turn on a structural observation: the length of adjacent runs, a single counter, a careful state scan, or the offset between two sets of points. See the structure and the search vanishes.

The pattern

The recurring move is summarize before you compare. Rather than enumerate every substring, compress the string into runs of identical characters and reason about neighboring run lengths — the count of valid groupings depends only on the smaller of two adjacent runs.

Some problems are even simpler than they look: a question dressed up as "balanced halves" reduces to comparing one tally on each side. Others are messy in the opposite direction — validity rules with signs, decimals, and exponents resist clever math, so the honest tool is a careful flag-based scan or finite-state machine that walks the string once and tracks what has legally been seen.

For grids, the insight is work in offset space: instead of overlaying images directly, collect the coordinates of set points and tally the translation vector between every pair; the most frequent shift is the best overlap. The unifying idea: the answer lives in a derived quantity — runs, counts, states, or offsets — not the raw text.

The problems

• Count Binary Substrings — compress into consecutive run lengths; each adjacent pair contributes min(prev_run, cur_run) balanced substrings.
• Determine if String Halves Are Alike — just compare the vowel count of the two halves; no rearranging needed.
• Valid Number — walk the string once with flags (or an FSM) tracking digit, dot, sign, and exponent rules to handle the messy cases.
• Image Overlap — record the coordinates of 1-cells, tally the translation offset between every cross-pair, and return the most common offset's count.

Key takeaways

• Summarize into runs — adjacent run lengths answer substring counts.
• Some "hard" reductions are a tally — count, don't restructure.
• Messy rules want an FSM — one careful flagged pass, not cleverness.
• Shift offsets beat overlays — tally translations between point sets.