We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Prefix and Suffix Pairs II

Number: 3305

Difficulty: Hard

Paid? No

Companies: Capital One, Autodesk

Problem Description

Given an array of strings words, count the number of index pairs (i, j) with i < j such that words[i] is both a prefix and a suffix of words[j]. In other words, for a valid pair, words[j] should begin with words[i] and end with words[i].

Key Insights

  • For a pair (i, j) to be valid, words[i] must be one of the “borders” of words[j] (a string that is both its prefix and suffix).
  • Rather than comparing each pair naively, we can precompute for each word the set of its borders using techniques such as the KMP prefix function.
  • An offline approach is helpful where we iterate through the list in reverse order. For each word (treated as a potential S word), we add counts for each of its border strings to a global map.
  • Then, when processing an earlier word (as a candidate prefix), we simply add how many future words have that word as one of their borders.
  • The overall work is proportional to the total length of the strings (which is bounded by 5×10^5), making the approach efficient.

Space and Time Complexity

Time Complexity: O(total length of all words) — each word’s borders are computed in linear time relative to its length. Space Complexity: O(total length of all words) — to store the prefix function for computing borders and the frequency map for candidate border strings.

Solution

The main idea is to reframe the problem: instead of trying to match each possible pair on the fly, we count for each word j (as the “S” word) all of its border strings (which include the full length string and any proper border). We will iterate over the words from right to left and update a frequency map (futureMap) where each border string key’s value is the number of words (with index greater than the current index) that have that string as a border. Then, when processing a word at index i, we simply add the count from futureMap[words[i]] (if any) to our result. Finally, we compute the borders of words[i] (using the KMP prefix function) and update futureMap accordingly so that future indices (i.e., with smaller index) can match against the current word’s contributions.

Data Structures and Techniques:

  • Hash Map: To store the count of how many times a candidate border string appears as a border for some j (j > i).
  • KMP Prefix Function: To derive all border lengths of a word efficiently.
  • Reverse Iteration: Ensures that when we process a candidate word at index i, all words with index j > i have already been processed and their border counts recorded.

Gotchas:

  • When computing borders via the prefix function, be sure to include the whole word (which is always a valid border for itself) as well as all proper borders.
  • Beware of the order condition (i < j); processing from right to left simplifies the counting logic.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with inline comments.

def countPrefixSuffixPairs(words):
    # Helper function to compute all borders using KMP prefix function.
    def get_borders(word):
        n = len(word)
        # Compute the prefix function (pi) for the word.
        pi = [0] * n
        for i in range(1, n):
            j = pi[i-1]
            while j > 0 and word[i] != word[j]:
                j = pi[j-1]
            if word[i] == word[j]:
                j += 1
            pi[i] = j
        # Collect all borders by repeatedly going to the value of pi for the last index.
        borders = []
        length = n
        while length:
            borders.append(word[:length])
            length = pi[length - 1]
        return borders

    result = 0
    futureMap = {}  # Dictionary to store border string frequency for indices > current.

    # Iterate words from rightmost to leftmost.
    for word in reversed(words):
        # If the current word appears as a border in any future word, add that count.
        result += futureMap.get(word, 0)
        # Compute all borders of the current word.
        borders = get_borders(word)
        # Add each border to the futureMap.
        for border in borders:
            futureMap[border] = futureMap.get(border, 0) + 1
    return result

# Example usage:
words1 = ["a", "aba", "ababa", "aa"]
print(countPrefixSuffixPairs(words1))  # Expected Output: 4
← Back to All Questions