Count Prefix and Suffix Pairs I

Easy

#2710Time: O(N^2 * L), where `N` is the number of words and `L` is the maximum length of a word. We have two nested loops giving `O(N^2)` pairs. For each pair, `startsWith` and `endsWith` operations take up to `O(L)` time.Space: O(1), as we only use a constant amount of extra space for the counter and loop variables.2 companies

Patterns

String Matching Rolling Hash Hash Function

Data structures

Array String Trie

Companies

Capital One Autodesk

Prompt

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 <= 50
1 <= words[i].length <= 10
words[i] consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to iterate through all possible pairs of indices (i, j) where i < j and check if words[i] is both a prefix and a suffix of words[j]. This involves nested loops and direct string comparisons.

Algorithm

Initialize a counter variable count to zero.
Use two nested loops to generate all unique pairs of indices (i, j) such that i < j. The outer loop runs from i = 0 to words.length - 1, and the inner loop runs from j = i + 1 to words.length - 1.
Inside the inner loop, for each pair of strings words[i] and words[j], perform the required check.
Use built-in string functions to check the conditions: words[j].startsWith(words[i]) for the prefix condition and words[j].endsWith(words[i]) for the suffix condition.
If both functions return true, it means we have found a valid pair, so we increment our count.
After the loops complete, count holds the total number of such pairs, which is then returned.

Walkthrough

We initialize a counter variable count to zero. We use two nested loops to generate all unique pairs of indices (i, j) such that i is less than j. The outer loop runs from i = 0 to words.length - 1, and the inner loop runs from j = i + 1 to words.length - 1. Inside the inner loop, for each pair of strings words[i] and words[j], we perform the required check. A simple optimization is to first check if the length of words[i] is greater than the length of words[j]. If it is, words[i] cannot be a prefix or suffix, so we can skip to the next pair. We then use built-in string functions to check the conditions. words[j].startsWith(words[i]) checks for the prefix condition, and words[j].endsWith(words[i]) checks for the suffix condition. If both functions return true, it means we have found a valid pair, so we increment our count. After the loops complete, count holds the total number of such pairs.

1class Solution {2    public int countPrefixAndSuffixPairs(String[] words) {3        int count = 0;4        int n = words.length;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                String str1 = words[i];8                String str2 = words[j];9                if (str2.startsWith(str1) && str2.endsWith(str1)) {10                    count++;11                }12            }13        }14        return count;15    }16}

Complexity

Time

O(N^2 * L), where `N` is the number of words and `L` is the maximum length of a word. We have two nested loops giving `O(N^2)` pairs. For each pair, `startsWith` and `endsWith` operations take up to `O(L)` time.

Space

O(1), as we only use a constant amount of extra space for the counter and loop variables.

Trade-offs

Pros

Simple to understand and implement.
Very low memory usage.
Sufficiently fast for the given problem constraints.

Cons

Less efficient than other possible solutions. The time complexity is quadratic in the number of words, which would be too slow for larger inputs.

A more optimized approach involves iterating through the words array once. For each word, we find all of its prefixes that are also suffixes. Then, we use a hash map to efficiently look up how many times these special "prefix-suffix" strings have appeared as complete words earlier in the array.

Algorithm

Initialize count = 0.
Initialize an empty HashMap<String, Integer> called freq to store the frequency of words seen so far.
Iterate through each word in the words array.
For the current word, iterate through its possible prefix lengths k from 1 to word.length().
Get the prefix p of length k.
Check if word also ends with p.
If it does, look up p in the freq map. Add the frequency of p (or 0 if not present) to count.
After checking all prefixes for the current word, update its frequency in the freq map.
After iterating through all words, return count.

Walkthrough

This method avoids the O(N^2) pair-wise comparison by processing the array in a single pass. We maintain a hash map to store the frequency of words encountered so far. We initialize a counter count to zero and a HashMap<String, Integer> to store word frequencies. We iterate through each word in the words array. For each word, we need to find how many previously seen words are a prefix-and-suffix of the current word. To do this, we iterate through all possible prefixes of the current word. For each prefix, we check if it's also a suffix of the word. If a prefix is also a suffix, we look it up in our frequency map. If it exists, we add its stored frequency to our total count. This is because every previous occurrence of that string forms a valid pair with the current word. After checking all prefixes for the current word, we update the frequency map with the current word itself, incrementing its count or adding it if it's the first time we've seen it. This makes it available for subsequent words in the array.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int countPrefixAndSuffixPairs(String[] words) {6        int count = 0;7        // This map will store the frequency of each word encountered so far.8        Map<String, Integer> freq = new HashMap<>();9 10        for (String word : words) {11            // For the current word, check all its prefixes.12            for (int k = 1; k <= word.length(); k++) {13                String prefix = word.substring(0, k);14                // Check if the prefix is also a suffix.15                if (word.endsWith(prefix)) {16                    // If this prefix has been seen before as a full word,17                    // it forms a valid pair with the current word.18                    // Add the number of times it has appeared to the count.19                    count += freq.getOrDefault(prefix, 0);20                }21            }22            // Update the frequency map with the current word.23            freq.put(word, freq.getOrDefault(word, 0) + 1);24        }25        return count;26    }27}

Complexity

Time

O(N * L^2), where `N` is the number of words and `L` is the maximum length of a word. The outer loop runs `N` times. The inner loop runs `L` times. Inside the inner loop, `substring`, `endsWith`, and `getOrDefault` (with string hashing) each take `O(L)` time in the worst case. This results in `N * L * L = O(N * L^2)`.

Space

O(N * L), where `N` is the number of words and `L` is the maximum length of a word. In the worst case, all words are unique and the hash map will store all of them, consuming space proportional to the total number of characters in the input.

Trade-offs

Pros

More efficient time complexity compared to the brute-force approach, especially for larger N.
Processes the array in a single pass.

Cons

Uses extra space to store word frequencies, unlike the O(1) space brute-force method.
Slightly more complex to implement due to the use of a hash map and prefix generation logic.

Solutions

Solution

1class Solution {2public3  int countPrefixSuffixPairs(String[] words) {4    int ans = 0;5    int n = words.length;6    for (int i = 0; i < n; ++i) {7      String s = words[i];8      for (int j = i + 1; j < n; ++j) {9        String t = words[j];10        if (t.startsWith(s) && t.endsWith(s)) {11          ++ans;12        }13      }14    }15    return ans;16  }17}

1class Solution {2public:3  int countPrefixSuffixPairs(vector<string> &words) {4    int ans = 0;5    int n = words.size();6    for (int i = 0; i < n; ++i) {7      string s = words[i];8      for (int j = i + 1; j < n; ++j) {9        string t = words[j];10        if (t.find(s) == 0 && t.rfind(s) == t.length() - s.length()) {11          ++ans;12        }13      }14    }15    return ans;16  }17};

1class Solution:2    def countPrefixSuffixPairs(self, words: List[str]) -> int: ans = 0 for i, s in enumerate(words): for t in words[i + 1:]: ans += t . endswith(s) and t . startswith(s) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem