Count Prefix and Suffix Pairs I - Solution & Explanation
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)returnstrueifstr1is both a prefix and a suffix ofstr2, andfalseotherwise.
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 <= 501 <= words[i].length <= 10words[i]consists only of lowercase English letters.
Approach Overview
Problem Overview: You are given an array of strings words. Count pairs (i, j) where i < j and words[i] appears as both a prefix and a suffix of words[j]. The task reduces to checking whether one string matches the beginning and ending segments of another string.
Approach 1: Brute Force Comparison (Time: O(n^2 * m), Space: O(1))
Check every pair of strings. For each i and j where i < j, verify whether words[j] starts with words[i] and also ends with the same string. Most languages provide direct operations like startswith and endswith, which internally compare characters one by one. If both conditions hold, increment the count.
The complexity comes from examining every pair of words (O(n^2)) and performing string comparisons up to the length of the smaller word (O(m)). This approach works well for small inputs and clearly demonstrates the core logic of the problem. It relies only on basic array iteration and simple string operations.
Approach 2: Optimized Using String Matching / Hashing (Time: O(n^2), Space: O(n * m))
You can reduce repeated character comparisons by preprocessing strings with hashing or structured string-matching techniques. Using a rolling hash or prefix hash array, compute hash values for every prefix and suffix of each string. When comparing words[i] with words[j], compare their hash values instead of characters. If the prefix hash of length len(words[i]) in words[j] matches the full hash of words[i], and the suffix hash matches as well, the pair is valid.
This turns each prefix and suffix check into an O(1) operation after preprocessing. The overall pair iteration still takes O(n^2), but individual string comparisons become constant time. Techniques like string matching and rolling hash are commonly used in competitive programming to avoid repeated scans of the same substrings.
Recommended for interviews: Start with the brute force approach. It shows you understand the problem: iterate pairs and verify prefix and suffix conditions. Once that’s clear, mention the optimization using hashing or other string-matching techniques to avoid repeated character comparisons. Interviewers typically expect the simple pair-check solution first, followed by discussion of faster substring comparison strategies.
Approach 1: Brute Force Approach
This approach involves checking each possible pair of indices (i, j) to determine if words[i] is both a prefix and suffix of words[j]. We will simply iterate over all pairs of the words and apply the prefix and suffix condition.
This Python function counts the number of pairs (i, j) such that words[i] is both a prefix and suffix of words[j]. It defines a helper function is_prefix_and_suffix to perform this check and iterates over all pairs of the array to count the valid ones.
Complexity
Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of a word.
Space Complexity: O(1) as we are using constant extra space.
Approach 2: Optimized Approach Using String Matching
An optimized approach would require reducing the number of unnecessary comparisons. Since the constraints are small, a direct approach is feasible. However, if required, we can attempt to use advanced techniques such as hashing or Rabin-Karp algorithm for prefix-suffix matching which can potentially reduce time complexity by ensuring we're not redundantly checking characters.
This optimized Python solution preprocesses each word to store all possible prefixes in a dictionary. Then for each word, it fetches potential matches from the dictionary where words are prefixes and checks them for suffix property.
Complexity
Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. The improvement comes from reducing unnecessary suffix checks.
Space Complexity: O(n * m) due to storing prefixes.
Approach 3: Enumeration
We can enumerate all index pairs (i, j), where i < j, and then determine whether words[i] is a prefix or suffix of words[j]. If it is, we increment the count.
The time complexity is O(n^2 times m), where n and m are the length of words and the maximum length of the strings, respectively.
Code
Python
Java
C++
Go
TypeScript
Approach 4: 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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of a word. |
| Optimized Approach Using String Matching | Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. The improvement comes from reducing unnecessary suffix checks. |
| Enumeration | — |
| Trie | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix & Suffix Check | O(n^2 * m) | O(1) | Best for understanding the problem or when constraints are small |
| Rolling Hash / String Matching Optimization | O(n^2) | O(n * m) | When repeated string comparisons are expensive and faster substring checks are needed |
Video Solution
Count Prefix and Suffix Pairs I & II - Leetcode 3042 & 3045 - Python • NeetCodeIO • 12,892 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Prefix and Suffix Pairs I easy or hard?
Count Prefix and Suffix Pairs I Python/Java solution
How to solve Count Prefix and Suffix Pairs I in O(n)?
What is the best approach for Count Prefix and Suffix Pairs I?
Is Count Prefix and Suffix Pairs I asked at Google/Amazon/Meta?
What data structure is used in Count Prefix and Suffix Pairs I?
What is the time complexity of Count Prefix and Suffix Pairs I?
Ready to solve this problem?
Practice Count Prefix and Suffix Pairs I with our built-in code editor and test cases.
Practice on FleetCode