Count Prefix and Suffix Pairs II

Count Prefix and Suffix Pairs II

What is this problem about?

The "Count Prefix and Suffix Pairs II interview question" is the highly optimized version of the prefix-suffix task. You need to count pairs $(i, j)$ with $i < j$ where $words[i]$ is both a prefix and a suffix of $words[j]$. However, the constraints are significantly larger ($N = 10^5$), meaning the $O(N^2)$ brute-force solution will fail. You must find a way to count these matches in near-linear time.

Why is this asked in interviews?

Uber and Samsung ask the "Count Prefix and Suffix Pairs II coding problem" to evaluate a candidate's knowledge of advanced string structures like Tries or Rolling Hashes. It requires the creative insight to transform two constraints (prefix and suffix) into a single search key. It's a high-level "String interview pattern" problem that tests architectural thinking.

Algorithmic pattern used

This problem is solved using a Trie of Pairs or Hash Map of Prefix-Suffix Hashes.

1. The Combined Key: A string $W$ has a prefix-suffix pair of length $L$ if $W[0...L-1] == W[|W|-L...|W|-1]$. Instead of checking both, we can store each character as a pair $(W[i], W[|W|-1-i])$.
2. Trie of Pairs: Build a Trie where each node represents a pair of characters. For a word "abc", the path in the Trie would be $(a, c) ightarrow (b, b) ightarrow (c, a)$.
3. Counting:
   • As you traverse the Trie for a new word, if you reach a node that was the end of a previous word, add that node's frequency to your total.
   • Increment the frequency of the current word's end node in the Trie.
4. Alternative: Use Rolling Hash to represent the combined (prefix, suffix) property and a hash map to count occurrences.

Example explanation

Words: ["aba", "ababa"]

1. For "aba":
   • Pairs: (a,a), (b,b), (a,a).
   • Traverse Trie with these pairs. Increment end node. Total count = 0.
2. For "ababa":
   • Pairs: (a,a), (b,b), (a,a), (b,b), (a,a).
   • Traverse. After 3 pairs, we reach the node representing "aba". Add its frequency (1) to total. Result: 1.

Common mistakes candidates make

• Double Tries: Building two separate Tries (one for prefixes, one for suffixes) and trying to intersect them. This is much harder to manage than the "Trie of Pairs."
• Memory Limit: Creating $O(N \cdot L)$ nodes in a Trie can exceed memory limits if not careful. Using a Hash Map for Trie children or using rolling hashes is often safer.
• Hash Collisions: If using rolling hash, failing to use a double hash or a large enough prime.

Interview preparation tip

Practice "mapping multiple constraints to a single key." This is a recurring theme in "Hard" interview questions. If you can combine two properties (prefix and suffix) into one structure, you can often reduce the search time from $O(N)$ to $O(1)$ or $O(L)$.