Count Prefix and Suffix Pairs I

Count Prefix and Suffix Pairs I

What is this problem about?

The "Count Prefix and Suffix Pairs I interview question" asks you to find the number of pairs of strings $(words[i], words[j])$ such that $i < j$ and $words[i]$ is BOTH a prefix and a suffix of $words[j]$. For example, if $words[i] = "aba"$ and $words[j] = "ababa"$, the condition is met because "aba" starts and ends "ababa".

Why is this asked in interviews?

Companies like Meta and Google ask the "Count Prefix and Suffix Pairs I coding problem" to test basic string manipulation and understanding of subsequences versus affixes. While the "I" version allows for a simpler $O(N^2 \cdot L)$ approach, it serves as a logic check before introducing more complex requirements or larger constraints in the "II" version.

Algorithmic pattern used

This problem follows the String Matching and Nested Loops pattern.

1. Outer Loop: Iterate through strings with index $i$.
2. Inner Loop: Iterate through strings with index $j > i$.
3. Condition Check:
   • Check if words[j].startsWith(words[i]).
   • Check if words[j].endsWith(words[i]).
4. Optimization: Skip the check if words[i].length() > words[j].length().

Example explanation

Words: ["a", "aba", "ababa", "aa"]

• Pair (0, 1): "a" is prefix and suffix of "aba". (Count = 1)
• Pair (0, 2): "a" is prefix and suffix of "ababa". (Count = 2)
• Pair (1, 2): "aba" is prefix and suffix of "ababa". (Count = 3)
• Pair (0, 3): "a" is prefix and suffix of "aa". (Count = 4) Result: 4.

Common mistakes candidates make

• Subsegment Confusion: Checking if $words[i]$ is just "contained" anywhere in $words[j]$ rather than strictly at the start and end.
• Index Errors: Mixing up the indices $i$ and $j$, or checking $i=j$.
• Performance: Not realizing that endsWith can be implemented efficiently without creating new string slices.

Interview preparation tip

Be comfortable with your language's standard string library. Knowing the time complexity of startsWith and endsWith (usually linear in the length of the shorter string) is crucial for accurate big-O analysis.