String Parsing, Tokenization, And Validation

What's being tested

String parsing under strict format rules: splitting input into meaningful tokens while rejecting malformed cases early. Interviewers probe whether you can combine tokenization, validation, and simple data structures like stacks without losing edge cases around whitespace, signs, overflow, or delimiters.

Patterns & templates

• Single-pass lexer — scan with index i, emit tokens, validate state transitions; O(n) time, O(1) or O(n) space.

• Parser state machine — track expected token type: number, operator, bracket, word, or end; catches 1++2, +1, and trailing operators.

• Safe integer accumulation — build numbers digit by digit using bounds checks before value = value * 10 + digit; enforce 32-bit range.

• Stack matching for brackets — push opening chars, pop on closing chars, compare via map; O(n) time, O(n) worst-case space.

• Whitespace-preserving tokenization — separate word tokens from space runs; reverse only words or rebuild with original spacing rules.

• Two-pointer in-place string/array edits — compact, reverse, or swap segments without extra copies; watch mutable vs immutable language constraints.

• Backtracking subsets — sort first for duplicate handling, recurse with start index; skip duplicates using if i > start && nums[i] == nums[i-1].

Common pitfalls

Pitfall: Treating parsing as split() only; strict validators usually require character-level control over empty tokens, leading zeros, signs, and spaces.

Pitfall: Checking overflow after arithmetic; in fixed-width languages, validate before multiply/add to avoid undefined or wrapped results.

Pitfall: Normalizing whitespace accidentally when the requirement says preserve original spaces, tabs, or relative spacing positions.

Practice these

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