#3045

Hard

LeetCode Problem Workspace

Count Prefix and Suffix Pairs II

Count the number of index pairs in a string array where one word is both a prefix and suffix of another using array and string patterns.

array string trie rolling hash string matching

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.

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.

terminal

Solution

Solution 1: Trie

We can treat each string $s$ in the string array as a list of character pairs, where each character pair $(s[i], s[m - i - 1])$ represents the $i$th character pair of the prefix and suffix of string $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Node:
    __slots__ = ["children", "cnt"]

    def __init__(self):
        self.children = {}
        self.cnt = 0


class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        ans = 0
        trie = Node()
        for s in words:
            node = trie
            for p in zip(s, reversed(s)):
                if p not in node.children:
                    node.children[p] = Node()
                node = node.children[p]
                ans += node.cnt
            node.cnt += 1
        return ans

Continue Practicing

#3042 count prefix and suffix pairs i #3291 minimum number of valid strings to form target i #3292 minimum number of valid strings to form target ii