String Processing And Character Mapping

What's being tested

These problems test character-level string processing: normalization, frequency counting, positional mapping, anagram detection, and composing substitution dictionaries. You must translate ambiguous requirements—case, punctuation, duplicate words, ties, malformed mappings—into deterministic algorithms with clear time and space bounds.

Patterns & templates

• Normalize once with lower(), isalpha(), or an explicit character policy; preserve original tokens only when output or tie-breaking requires them.

• Anagram detection uses a 26-count vector, sorted-character key, or Counter; prefer counting for fixed alphabets: O(k) per word.

• Dictionary-constrained decoding groups vocabulary by signature, then backtracks or validates candidates while tracking consumed words and ambiguity.

• Character substitution maps use dict lookups; compose mappings as composed[c] = second[first[c]], validating bijection and missing keys.

• Per-word letter span is max(position) - min(position) over normalized letters; initialize bounds safely and ignore punctuation explicitly.

• Stable tie handling should be specified before coding: retain first maximum, lexicographically smallest word, or return every tied result.

• Complexity accounting should use total input length N; one-pass scans are O(N) time and O(A + W) space for alphabet size A and vocabulary size W.

Common pitfalls

Pitfall: Treating punctuation or uppercase letters inconsistently can produce different signatures, spans, or decoded output; state the normalization contract first.

Pitfall: Assuming an anagram has one dictionary match; preserve candidate lists and define how repeated words or ambiguity are resolved.

Pitfall: Composing substitutions in the wrong order; test a character through both transformations and verify injectivity when mappings claim to be bijective.

Practice these

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