3045. Count Prefix and Suffix Pairs II

Problem Description

The problem presents us with an array of strings words, where each element is a string. We are tasked to determine the number of unique index pairs (i, j) such that the string at index i is both a prefix (the beginning part) and a suffix (the ending part) of the string at index j, with the additional condition that i must be less than j.

For example, if the words array contains ["apple", "applepie", "pie"], then the string "apple" is both a prefix and a suffix of "applepie", forming a valid pair of indices (0, 1).

The challenge is to count all such pairs in the given array, taking into consideration that the strings can be of any length and the array can contain a large number of strings.

Intuition

The straightforward approach to this problem would be to compare every possible pair of strings and check if the conditions of being a prefix and suffix are met. However, this naive approach could be very inefficient because it would require a lot of redundant comparison especially when there are repeating patterns in the strings.

To optimize the process, we should try to find a way that can help us identify the prefix-suffix relationship faster. This brings us to the core of the solution - Trie data structure. Tries are often used for efficiently searching for prefixes in a set of strings. But for our problem, we need to check for both prefixes and suffixes simultaneously.

To achieve this, we introduce a modified trie that holds pairs of characters. Each pair is composed of a character from the prefix and a character from the suffix of the same position in the string. For example, for string "ababa", the pairs would be (a,a), (b,b), (a,a).

While inserting these pairs into the trie, we maintain a count at each node, representing how many times a particular prefix-suffix pair has been seen thus far. When we iterate over a new string to insert its character pairs into the trie, we can simultaneously calculate the number of times a subtree's character pairs have appeared before. This allows us to efficiently count the number of valid i < j pairs, where isPrefixAndSuffix(words[i], words[j]) is true, without having to explicitly check every combination.

The given solution code implements a Trie with the specified modification and efficiently computes the count of qualifying index pairs.

Learn more about Trie patterns.

Solution Approach

In the solution approach, we are utilizing a Trie data structure. Traditionally, a trie is used for storing and searching for strings based on their prefixes. In our case, we need to consider both the prefix and suffix simultaneously. The main algorithms and patterns used in our solution are:

• Trie Construction: The trie is constructed not on single characters but on pairs of characters. Each node in the trie represents a pair of (prefix_char, suffix_char). If the string is "ababa", the pairs inserted would be (a, a), (b, b), and (a, a). The trie is used to store all possible prefix-suffix pairs that we encounter when iterating through the words.

• Trie Node Structure: Each node in the trie contains a dictionary children that maps character pairs to their corresponding child nodes. It also has a counter cnt, which indicates the number of times the particular prefix-suffix pair (represented by the path to this node) has been encountered so far.

• Inserting into the Trie: For each string s, we iterate through the characters, creating a pair (s[i], s[m-i-1]) which contains the i-th character from the start and end of the string. We insert this pair into the trie. If the pair doesn't exist, we create a new node.

• Searching and Counting: While inserting character pairs of a string, we traverse the trie based on these pairs. We also increment the count of how often we have seen the prefix-suffix pair, which is hosted on the trie node.

• Utility of the Count: As we insert a string's character pairs into the trie, we simultaneously add the count at the current node to our overall count ans. This count at the node represents how many times we have previously seen this prefix-suffix pair, which directly corresponds to how many valid pairs (i, j) we can form with strings encountered so far for which i < j.

• Efficient Counting: By using this trie structure, we can insert each string and efficiently increment our answer ans without having to directly compare the strings. This approach reduces the complexity from potentially quadratic time (considering all pairs of strings) to linear time, relative to the total number of characters in all strings.

1class Node:
2    __slots__ = ["children", "cnt"]
3
4    def __init__(self):
5        self.children = {}
6        self.cnt = 0
7
8
9class Solution:
10    def countPrefixSuffixPairs(self, words: List[str]) -> int:
11        ans = 0
12        trie = Node()
13        for s in words:
14            node = trie
15            for p in zip(s, reversed(s)):
16                if p not in node.children:
17                    node.children[p] = Node()
18                node = node.children[p]
19                ans += node.cnt
20            node.cnt += 1
21        return ans

The above code snippets show how each part of the trie is created, used, and contributes to solving the problem efficiently by using the trie as a sophisticated counting tool.

Example Walkthrough

Let's say we have an array of words ["one", "onenote", "note"]. We have to find all unique index pairs (i, j) where i < j and words[i] is both a prefix and a suffix of words[j].

Here’s a step-by-step process using the solution approach:

1. Initialize an empty trie and a variable ans to keep count of the valid index pairs found.

2. Start iterating through each word in words.

3. For each word such as "one", create pairs from its prefix and suffix characters. Here we would get: ('o', 'e'), ('n', 'n'), ('e', 'o').

4. Insert each pair into the trie:

   • For the first pair ('o', 'e'), as it doesn't exist in the trie yet, we create a new node and move to it.
   • For the second pair ('n', 'n'), again, create a new node and move to it.
   • For the third pair ('e', 'o'), create a new node and move to it.

5. At the end of insertion of the character pairs from "one", the current node's count is increased by 1.

6. Move on to the next word "onenote". Start inserting pairs: ('o', 'e'), ('n', 't'), ('e', 'o'), ('n', 'n'), ('o', 'e').

   • When we insert the first pair ('o', 'e'), we find it's already in the trie, so we just move to that node and increment ans by the count at the node (which is 0 at this point since no other strings have been encountered that end with 'e' and start with 'o').
   • Continue inserting pairs, creating new nodes for those which don't already exist (('n', 't') and ('e', 'o')), and incrementing ans when we encounter existing nodes (like for the last pair ('o', 'e'), ans would be incremented again).

7. The pattern repeats for the last word "note". The pairs here are: ('n', 'e'), ('o', 't'), ('t', 'o'), ('e', 'n').

   • Since none of these character pairs exist in the trie yet, new nodes will be created, and ans remains unchanged during this insertion.

8. At the end of this process, the ans variable contains the total count of valid (i, j) index pairs where word[i] is a prefix and suffix of word[j].

Following the above steps the ans will be 1 because "one" is both a prefix and suffix of "onenote". Therefore, we have a valid index pair (0, 1). The word "note" does not share the prefix and suffix relation with any other string in the array, so no more pairs are added.

The solution approach efficiently finds this count without having to compare each pair of words directly, which would be less efficient, especially as the array of words grows larger.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n * m) where n is the number of words in the input list words and m is the maximum length of a word in words. This is because for each word, the code iterates through each character twice - once in the original order and once in the reversed order. In the worst case, it will visit each node up to m times, and there are n words to process.

The space complexity of the code is also O(n * m) because in the worst case, each character pair (p) of every word might be unique, constituting a new path in the trie. Since each unique pair would need a new node, this would require space proportional to the number of pairs, which is m for one word and n * m for all words.

Learn more about how to find time and space complexity quickly using problem constraints.