Exact Substring Matching And Highlighting

What's being tested

Tests exact substring matching across one or more source strings, then converting raw match positions into correctly tagged output. Interviewers are probing for clean interval generation, overlap/adjacency merging, deterministic handling of multiple sources, and bug-free string reconstruction.

Patterns & templates

• Brute-force matching with `find_all(text, pattern)` — loop using `str.find(pattern, start)`; advance by 1 to allow overlapping matches.

• Interval collection — convert every match to half-open [start, end) intervals; half-open bounds simplify merging and output slicing.

• Sort-and-merge intervals — sort by (start, end), then merge when next.start <= cur.end; use < if adjacent matches should stay separate.

• Multi-pattern search — for many source strings, use Aho-Corasick for `O(n + total_matches + total_pattern_length)` instead of nested scans.

• Output reconstruction — append unmatched text, opening tag, matched slice, closing tag; never mutate the string while iterating indices.

• Counting occurrences — keep a map like `source_id -> count` or `pattern -> count`; define whether overlapping occurrences count before coding.

• Edge-case template — handle empty sources, duplicate patterns, empty pattern strings, case sensitivity, punctuation, Unicode, and repeated adjacent matches.

Common pitfalls

Pitfall: Advancing `start += len(pattern)` misses overlapping matches like finding "aa" twice in "aaa".

Pitfall: Inserting tags directly into the original string shifts later indices and corrupts positions; build a new output buffer instead.

Pitfall: Forgetting to merge adjacent intervals can produce `<b>abc</b><b>def</b>` when the expected output is `<b>abcdef</b>`.

Practice these

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