Start by recognizing that for each word in the array, you need to check other words to see if it is both a prefix and a suffix. Using a Trie for fast prefix and suffix lookups can reduce unnecessary comparisons. Hashing or rolling hash can further optimize string matching to achieve efficient time complexity.
Problem Statement
You are given a 0-indexed array of strings called words. Define a boolean function isPrefixAndSuffix that returns true if a string str1 is both a prefix and suffix of another string str2.
Your task is to count all pairs of indices (i, j) with i < j such that isPrefixAndSuffix(words[i], words[j]) is true. For example, isPrefixAndSuffix("aba", "ababa") is true, but isPrefixAndSuffix("abc", "abcd") is false.
Examples
Example 1
Input: words = ["a","aba","ababa","aa"]
Output: 4
In this example, the counted index pairs are: i = 0 and j = 1 because isPrefixAndSuffix("a", "aba") is true. i = 0 and j = 2 because isPrefixAndSuffix("a", "ababa") is true. i = 0 and j = 3 because isPrefixAndSuffix("a", "aa") is true. i = 1 and j = 2 because isPrefixAndSuffix("aba", "ababa") is true. Therefore, the answer is 4.
Example 2
Input: words = ["pa","papa","ma","mama"]
Output: 2
In this example, the counted index pairs are: i = 0 and j = 1 because isPrefixAndSuffix("pa", "papa") is true. i = 2 and j = 3 because isPrefixAndSuffix("ma", "mama") is true. Therefore, the answer is 2.
Example 3
Input: words = ["abab","ab"]
Output: 0
In this example, the only valid index pair is i = 0 and j = 1, and isPrefixAndSuffix("abab", "ab") is false. Therefore, the answer is 0.
Constraints
- 1 <= words.length <= 105
- 1 <= words[i].length <= 105
- words[i] consists only of lowercase English letters.
- The sum of the lengths of all words[i] does not exceed 5 * 105.
Solution Approach
Brute-force check
Iterate over all index pairs (i, j) and check if words[i] is a prefix and suffix of words[j]. This works but fails for large arrays due to O(n^2 * k) time, where k is average word length.
Trie-based optimization
Build a forward Trie and a reversed Trie for words. For each word, search the Trie for matching prefixes and reversed Trie for suffixes. Count pairs efficiently by combining prefix and suffix hits, reducing redundant string comparisons.
Rolling hash enhancement
Compute rolling hashes for all words and their reverses. Compare hash values for prefix and suffix matches instead of full string comparisons. This reduces per-comparison cost and avoids repeated substring operations, making the algorithm scalable for large word arrays.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity depends on the approach: brute-force is O(n^2 * k), Trie-based is roughly O(n * k) with efficient lookups, and rolling hash reduces per comparison cost further. Space complexity includes storing Tries and hash arrays, which is O(total characters in words).
What Interviewers Usually Probe
- Do you consider both prefix and suffix simultaneously?
- Are you using a Trie or hash to avoid full string comparisons?
- How would you scale if words array has 100000 entries?
Common Pitfalls or Variants
Common pitfalls
- Attempting only prefix checks and ignoring suffix validation.
- Using nested loops without optimization leading to TLE.
- Not handling edge cases where a word is equal to another word completely.
Follow-up variants
- Count only prefix pairs without suffix requirement.
- Check for strict proper prefix and proper suffix excluding full equality.
- Find pairs where the combined length equals a target number.
How GhostInterview Helps
- Provides step-by-step Trie construction and traversal for prefix-suffix matching.
- Illustrates efficient use of rolling hash to replace repeated substring comparisons.
- Highlights patterns and failure modes to guide optimal pair counting in large arrays.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main idea behind Count Prefix and Suffix Pairs II?
The goal is to count index pairs where one word is both a prefix and suffix of another in a given array using efficient string matching.
Can this problem be solved without a Trie?
Yes, using rolling hashes or optimized substring comparisons, but Trie structures help reduce redundant prefix and suffix checks.
What are common performance pitfalls?
Nested loops without optimization lead to timeouts; ignoring suffix checks can give incorrect counts; not using efficient string matching increases complexity.
How does rolling hash improve performance?
Rolling hash converts string comparisons into integer comparisons, which is faster and avoids repeated substring operations.
Does GhostInterview cover Array plus String pattern in this problem?
Yes, it explains using array traversal combined with Trie and hash-based string matching to efficiently count prefix-suffix pairs.
Need direct help with Count Prefix and Suffix Pairs II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Count Prefix and Suffix Pairs II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Count all index pairs where one word is both a prefix and suffix of another, using efficient array and string checks.
Open problem page#3291 Minimum Number of Valid Strings to Form Target IUse dynamic programming to split target into the fewest prefixes that match any word prefix, while ruling out dead positions early.
Open problem page#3292 Minimum Number of Valid Strings to Form Target IICompute the minimum number of valid strings from an array needed to construct a given target string efficiently using dynamic programming.
Open problem page