Skip to main content
Talentd

Count Prefix and Suffix Pairs II - Solution & Explanation

HardArrayStringTrieRolling Hash24 min readAsked at: Samsung, Capital One, Uber +1
Practice this problem

Problem Statement

You are given a 0-indexed string array words.

Let's define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:

  • isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.

For example, isPrefixAndSuffix("aba", "ababa") is true because "aba" is a prefix of "ababa" and also a suffix, but isPrefixAndSuffix("abc", "abcd") is false.

Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.

 

Example 1:

Input: words = ["a","aba","ababa","aa"]
Output: 4
Explanation: 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
Explanation: 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
Explanation: 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.

Approach Overview

Problem Overview: You are given an array of strings. Count pairs (i, j) such that i < j and words[i] is both a prefix and a suffix of words[j]. The challenge comes from large input sizes, which makes naive pairwise string comparison too slow.

Approach 1: Brute Force String Comparison (O(n^2 · m) time, O(1) space)

Check every pair of indices (i, j) with i < j. For each pair, verify whether words[i] matches both the prefix and suffix of words[j]. Prefix comparison checks the first len(words[i]) characters, while suffix comparison checks the last len(words[i]). Each comparison costs up to O(m) where m is the string length. This results in O(n^2 · m) total time. The approach is straightforward and useful for understanding the requirement, but it becomes impractical when the number of strings grows.

Approach 2: Optimized Rolling Hash Matching (O(totalLength) average time, O(n) space)

Instead of comparing strings character by character, compute rolling hash values for prefixes and suffixes of each word. While scanning a word, build prefix and suffix hashes simultaneously. Whenever the prefix hash equals the suffix hash for length k, the substring is both a prefix and suffix candidate. Store previously seen words in a hash map keyed by their hash value. A constant-time hash lookup tells you how many earlier strings match the current prefix–suffix substring. This converts expensive string comparisons into fast integer comparisons.

The key idea: a string that is both prefix and suffix must have identical hash values from both directions. With precomputed powers and incremental hashing, each character contributes once, giving near linear complexity across all strings.

Some implementations also use a trie or prefix tree to track prefixes efficiently, but hashing usually gives simpler code and excellent performance.

Recommended for interviews: Start by explaining the brute force solution to show you understand the pair condition and prefix/suffix check. Then move to the hashing optimization. Interviewers expect you to eliminate repeated string comparisons using hashing or a string processing technique. The optimized approach demonstrates knowledge of rolling hashes and efficient substring matching.

Approach 1: Brute Force Approach

This approach involves iterating through each pair of strings and checking if one is both a prefix and suffix of the other. Although this might be simple to implement, it can be computationally expensive for large inputs.

This solution defines a helper function isPrefixAndSuffix to check if one string is both prefix and suffix of another. This check involves comparing the starting and ending segments of the second string with the first string.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 * m), where n is the number of words and m is the maximum length of a word. Space Complexity: O(1), as we're using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Optimized Approach Using Hashing

This approach utilizes hashing to optimize the searching of potential prefix and suffix pairs. By hashing potential prefixes and suffixes, we can reduce redundant checks, improving efficiency.

A hash table is employed to store prefixes and suffixes of each string for fast retrieval. This reduces the overhead of comparing each pair manually.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m). Space Complexity: O(n * m), where n is number of words and m is maximum length of a word.

Try this approach in the editor →

Approach 3: Naive Brute Force Approach

In this approach, we iterate over all possible pairs of indices (i, j) with i < j and check whether the word at index i is both a prefix and a suffix of the word at index j. Although simple, this approach is inefficient for large datasets due to its O(n*m) complexity, where n is the number of words and m is the average length of the words.

This solution iteratively checks each pair of words in the list using the `isPrefixAndSuffix` function. It verifies if a word is both a prefix and a suffix of another word, maintaining a count of such cases.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n^2 * m), where n is the number of words and m is the average length of the words. The space complexity is O(1) as no extra space proportional to input is used.

Try this approach in the editor →

Approach 4: Optimized Approach Using KMP Algorithm

The Knuth-Morris-Pratt (KMP) algorithm can be used to find if a string is a prefix and suffix by preprocessing the pattern and avoiding redundant checks. The prefix function used in KMP gives valuable insight into repeated patterns in a string.

This C solution utilizes the KMP algorithm to efficiently determine if a word is a prefix and suffix by computing a longest proper prefix which is also suffix (LPS) for the concatenated form of the words.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is approximately O(n * m) and space complexity is O(m) due to the LPS array for each concatenation.

Try this approach in the editor →

Approach 5: 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 ith character pair of the prefix and suffix of string s.

We can use a trie to store all the character pairs, and then for each string s, we search for all the character pairs (s[i], s[m - i - 1]) in the trie, and add their counts to the answer.

The time complexity is O(n times m), and the space complexity is O(n times m). Here, n and m are the lengths of words and the maximum length of the strings, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2 * m), where n is the number of words and m is the maximum length of a word. Space Complexity: O(1), as we're using a constant amount of extra space.

Optimized Approach Using Hashing

Time Complexity: O(n * m). Space Complexity: O(n * m), where n is number of words and m is maximum length of a word.

Naive Brute Force Approach

The time complexity is O(n^2 * m), where n is the number of words and m is the average length of the words. The space complexity is O(1) as no extra space proportional to input is used.

Optimized Approach Using KMP Algorithm

The time complexity is approximately O(n * m) and space complexity is O(m) due to the LPS array for each concatenation.

Trie—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force String ComparisonO(n^2 · m)O(1)Small input sizes or when demonstrating the basic idea in interviews
Rolling Hash with Hash MapO(total string length)O(n)Large inputs where repeated prefix/suffix comparisons must be avoided

Video Solution

Count Prefix and Suffix Pairs I & II - Leetcode 3042 & 3045 - Python • NeetCodeIO • 12,895 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Count Prefix and Suffix Pairs II easy or hard?
Count Prefix and Suffix Pairs II is classified as a Hard problem. The difficulty comes from large constraints and the need to replace naive comparisons with hashing or advanced string matching techniques.
Count Prefix and Suffix Pairs II Python/Java solution
Python and Java solutions typically implement rolling hash with precomputed powers and a hash map storing previously seen strings. As each word is processed, prefix and suffix hashes are compared and matched against the map. This keeps the algorithm close to linear time.
How to solve Count Prefix and Suffix Pairs II in O(n)?
Process each word while maintaining rolling hashes for its prefixes and suffixes. When both hashes match for a certain length, the substring is both prefix and suffix. Use a hash map storing previously processed words by hash value to count matches in constant time. This avoids pairwise comparisons and scales linearly with the total input size.
What is the best approach for Count Prefix and Suffix Pairs II?
The most efficient approach uses rolling hash combined with a hash map. While scanning each word, compute prefix and suffix hashes and check when they match. Each matching prefix-suffix substring can be looked up in a map of previously seen words, allowing the pair count to be updated in constant time.
Is Count Prefix and Suffix Pairs II asked at Google/Amazon/Meta?
Problems involving prefix-suffix matching, rolling hashes, and trie structures appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test knowledge of string hashing, substring matching, and efficient counting techniques.
What data structure is used in Count Prefix and Suffix Pairs II?
Common solutions use a hash map with rolling hash values to represent strings efficiently. Some implementations also use a trie to track prefixes and detect matches while inserting characters. Both approaches aim to avoid repeated string comparisons.
What is the time complexity of Count Prefix and Suffix Pairs II?
The brute force solution runs in O(n^2 · m) where n is the number of strings and m is the average string length. The optimized rolling hash approach processes characters once and performs constant-time hash lookups, resulting in roughly O(total string length) time with O(n) extra space.

Ready to solve this problem?

Practice Count Prefix and Suffix Pairs II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Add and Search Words Data Structure

Next

Implement Trie (Prefix Tree)