Watch 10 video solutions for Count Prefix and Suffix Pairs I, a easy level problem involving Array, String, Trie. This walkthrough by NeetCodeIO has 12,395 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 501 <= words[i].length <= 10words[i] consists only of lowercase English letters.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 | 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 |