String Parsing, Palindromes, And Normalization

What's being tested

String parsing and palindrome reasoning are tested through two-pointer scans, dynamic programming, center expansion, and careful character normalization. Interviewers are probing whether you can turn ambiguous text rules into correct code with explicit complexity, clean edge-case handling, and readable implementation.

Patterns & templates

• Two-pointer palindrome check — isPal(l, r) runs in O(n) time, O(1) space; compare inward after normalization.

• One-deletion near-palindrome — on first mismatch, test isPal(l+1, r) or isPal(l, r-1); avoid branching recursively.

• Palindrome permutation — track odd character counts with Counter or a bitmask; valid iff odd count is <= 1.

• Center expansion for substrings — expand around 2n-1 centers; O(n^2) time, O(1) space; count each successful expansion.

• K-deletion palindrome DP — compute longest palindromic subsequence, answer n - LPS <= k; O(n^2) time, optimizable to O(n) space.

• Decimal string addition — scan right-to-left with carry; never cast to integer if arbitrary precision is required.

• Expression parsing without stack — maintain result, last_term, num, and op; handle precedence by adjusting the previous term.

Common pitfalls

Pitfall: Ignoring normalization rules: clarify case-folding, whitespace, punctuation, and Unicode before coding palindrome checks.

Pitfall: For near-palindromes, deleting repeatedly turns a one-deletion problem into exponential search; only branch once at the first mismatch.

Pitfall: In expression evaluation, integer division semantics vary; state whether truncation is toward zero, floor, or language default.

Practice these

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