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 <= 1051 <= words[i].length <= 105words[i] consists only of lowercase English letters.words[i] does not exceed 5 * 105.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.
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.
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.
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.
Time Complexity: O(n * m). Space Complexity: O(n * m), where n is number of words and m is maximum length of a word.
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.
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.
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.
The time complexity is approximately O(n * m) and space complexity is O(m) due to the LPS array for each concatenation.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force String Comparison | O(n^2 · m) | O(1) | Small input sizes or when demonstrating the basic idea in interviews |
| Rolling Hash with Hash Map | O(total string length) | O(n) | Large inputs where repeated prefix/suffix comparisons must be avoided |
Count Prefix and Suffix Pairs I & II - Leetcode 3042 & 3045 - Python • NeetCodeIO • 12,395 views views
Watch 7 more video solutions →Practice Count Prefix and Suffix Pairs II with our built-in code editor and test cases.
Practice on FleetCode