Scale Engineer

Count Prefix and Suffix Pairs II

Hard
#2713Time: O(N² * L), where N is the number of words and L is the maximum length of a word. For each of the O(N²) pairs, the `startsWith` and `endsWith` operations can take up to O(L) time.Space: O(1) extra space, as we only use a few variables to keep track of loops and the count.3 companies
Patterns
String MatchingRolling HashHash Function
Data structures
ArrayStringTrie
Companies
SamsungCapital OneAutodesk

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 <= 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.

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simulate the process described in the problem directly. We can use nested loops to generate every possible pair of indices (i, j) such that i < j. For each pair, we then check if words[i] is both a prefix and a suffix of words[j]. If it is, we increment a counter.

Algorithm

  • Initialize a counter count to 0.
  • Iterate through the words array with an outer loop for index i from 0 to n-1 (where n is the number of words).
  • Start an inner loop for index j from i+1 to n-1.
  • Inside the inner loop, check if words[i] is both a prefix and a suffix of words[j].
    • This can be done using built-in string functions like startsWith() and endsWith().
    • A necessary condition is that the length of words[i] must not be greater than the length of words[j].
  • If the condition holds true, increment the count.
  • After the loops complete, return the total count.

Walkthrough

This method involves a double loop. The outer loop iterates from the first word to the second-to-last word, picking words[i]. The inner loop iterates from words[i+1] to the last word, picking words[j]. For each pair (words[i], words[j]), we perform two checks: words[j].startsWith(words[i]) and words[j].endsWith(words[i]). If both checks return true, we've found a valid pair and we increment our result counter.

class Solution {    public long countPrefixSuffixPairs(String[] words) {        long count = 0;        int n = words.length;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                // The length check is implicitly handled by startsWith/endsWith                // but it's good practice to be aware of it.                if (words[j].startsWith(words[i]) && words[j].endsWith(words[i])) {                    count++;                }            }        }        return count;    }}

Complexity

Time

O(N² * L), where N is the number of words and L is the maximum length of a word. For each of the O(N²) pairs, the `startsWith` and `endsWith` operations can take up to O(L) time.

Space

O(1) extra space, as we only use a few variables to keep track of loops and the count.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no complex data structures.

Cons

  • Extremely inefficient for large inputs due to the nested loops.

  • The time complexity of O(N² * L) will cause a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

Solutions

class Node { Map < Integer , Node > children = new HashMap <>(); int cnt ; } class Solution { public long countPrefixSuffixPairs ( String [] words ) { long ans = 0 ; Node trie = new Node (); for ( String s : words ) { Node node = trie ; int m = s . length (); for ( int i = 0 ; i < m ; ++ i ) { int p = s . charAt ( i ) * 32 + s . charAt ( m - i - 1 ); node . children . putIfAbsent ( p , new Node ()); node = node . children . get ( p ); ans += node . cnt ; } ++ node . cnt ; } 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 →

Next problem