String And Numeric Representations

What's being tested

These problems test reasoning about string and numeric representations: counting/combinatorics over digit strings, efficient substring concatenation counts, and constrained path search on grids. Interviewers expect clean state modeling (parity, prefix/suffix counts, health states), asymptotic-efficient enumeration, and careful edge-case handling (leading zeros, overflow).

Patterns & templates

• Digit-by-digit counting via digit DP — model position, tight flag, and parity state; complexity ~O(len * states * 10), memoize results.

• Hash map counting using unordered_map — count occurrences of substrings/prefixes, then combine counts in O(1) per lookup; conversion with substr/stoi as needed.

• Prefix/suffix frequency precomputation — build counts for all prefixes/suffixes and multiply combinatorially to answer concatenation-count queries in O(n + m).

• Sliding-window / two-pointer for contiguous constraints — O(n) expand/contract; handle variable token sizes and empty-window boundaries.

• BFS / Dijkstra with extra state — encode (r,c,health) and prune by best-known health per cell; worst-case O(RCH) but prune aggressively.

• Bitmask / parity compression — represent digit-parity vector in an integer mask for O(1) state transitions and compact DP.

• Avoid repeated string ops — prefer indices and views or precomputed integer values to prevent O(n^2) substr overhead.

Common pitfalls

Pitfall: Treating numbers as plain integers ignores leading zeros and changes concatenation semantics — explicitly define and handle allowed leading zeros.

Pitfall: Double-counting symmetric pairs; enforce ordering (ordered vs unordered pairs) or divide appropriately.

Pitfall: Relying on repeated substr/stoi in hot loops causes timeouts and unexpected integer overflow; precompute or use rolling hashes.

Practice these — the practice cards below cover the canonical variants — solve all of them and time yourself.