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.
Determine if String Halves Are Alike
Core idea: Cut the string exactly in half. Count the vowels in the left half and the vowels in the right half, then ask one question: are those two counts equal? A vowel set turns "is this char a vowel?" into an O(1) lookup, so the whole thing is a single sweep of the string with two counters.
Problem, rephrased
You're handed a string s whose length is even. Split it down the middle into a left half a (the first len(s) // 2 characters) and a right half b (the rest). The two halves are called alike if they contain the same number of vowels.
Vowels are a, e, i, o, u, in both lowercase and uppercase. Return True if the halves are alike, False otherwise.
"book" -> True ("bo" has 1 vowel, "ok" has 1 vowel)
"textbook" -> False ("text" has 1 vowel, "book" has 2 vowels)
"AbCdEfGh" -> True ("AbCd" has 1, "EfGh" has 1)
Inputs / outputs
input s |
left half | vowels(left) | right half | vowels(right) | answer |
|---|---|---|---|---|---|
"book" |
"bo" |
1 | "ok" |
1 | True |
"textbook" |
"text" |
1 | "book" |
2 | False |
"AbCdEfGh" |
"AbCd" |
1 | "EfGh" |
1 | True |
"xy" |
"x" |
0 | "y" |
0 | True |
"aA" |
"a" |
1 | "A" |
1 | True |
The length is always even, so the split is always clean — no leftover middle character to worry about.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson