Solution Approach

The solution uses a Trie data structure to efficiently store and search for character pair patterns.

Data Structure Setup:

• We define a Node class with two attributes:
  • children: a dictionary to store child nodes, where keys are character pairs (char_from_start, char_from_end)
  • cnt: a counter to track how many strings end at this node

Algorithm Steps:

1. Initialize an empty trie and a counter ans = 0

2. Process each word in the array:

   • Start from the root of the trie
   • Create character pairs using zip(s, reversed(s)):
     • This pairs up s[0] with s[n-1], s[1] with s[n-2], and so on
     • For example, "aba" becomes pairs: ('a','a'), ('b','b'), ('a','a')

3. Traverse and build the trie for each character pair:

   • If the pair doesn't exist as a child, create a new node
   • Move to the child node corresponding to this pair
   • Add the current node's cnt to our answer (this represents all previously inserted strings that match up to this point)

4. Mark the end of the current string:

   • Increment node.cnt by 1 at the final position
   • This indicates that a complete string ends here

Why this works:

• When we traverse with a new string and encounter nodes with cnt > 0, it means there are shorter strings that are both prefixes and suffixes of the current string
• The pairing mechanism (s[i], s[m-i-1]) ensures that we're checking both prefix and suffix conditions simultaneously
• By accumulating the counts during traversal, we automatically count all valid (i, j) pairs where i < j

Time Complexity: O(n * m) where n is the number of words and m is the average length of each word.

Space Complexity: O(n * m) for storing the trie nodes.

Example Walkthrough

Let's walk through the solution with words = ["a", "aba", "ababa", "aa"].

Step 1: Process "a"

• Create pairs: zip("a", "a") → [('a', 'a')]
• Start at root, create child for ('a', 'a')
• No existing nodes, so ans = 0
• Mark end: set cnt = 1 at this node

Trie state:

root → ('a','a')[cnt=1]

Step 2: Process "aba"

• Create pairs: zip("aba", "aba") → [('a','a'), ('b','b'), ('a','a')]
• Traverse from root:
  • Move to ('a','a') child (exists), add its cnt=1 to answer → ans = 1
  • Create new child ('b','b') with cnt=0
  • Create new child ('a','a') with cnt=0
• Mark end: set cnt = 1 at final node

Trie state:

root → ('a','a')[cnt=1] → ('b','b')[cnt=0] → ('a','a')[cnt=1]

Found: "a" is both prefix and suffix of "aba" (pair (0,1))

Step 3: Process "ababa"

• Create pairs: zip("ababa", "ababa") → [('a','a'), ('b','b'), ('a','a'), ('b','b'), ('a','a')]
• Traverse from root:
  • Move to ('a','a'), add cnt=1 → ans = 2
  • Move to ('b','b'), add cnt=0 → ans = 2
  • Move to ('a','a'), add cnt=1 → ans = 3
  • Create new child ('b','b') with cnt=0
  • Create new child ('a','a') with cnt=0
• Mark end: set cnt = 1 at final node

Found: "a" and "aba" are both prefix and suffix of "ababa" (pairs (0,2) and (1,2))

Step 4: Process "aa"

• Create pairs: zip("aa", "aa") → [('a','a'), ('a','a')]
• Traverse from root:
  • Move to ('a','a'), add cnt=1 → ans = 4
  • Try to move to another ('a','a') child, but it doesn't exist from this node
  • Create new child ('a','a') with cnt=0
• Mark end: set cnt = 1 at final node

Found: "a" is both prefix and suffix of "aa" (pair (0,3))

Final answer: 4 (pairs: (0,1), (0,2), (1,2), (0,3))

Time and Space Complexity

The time complexity is O(n × m), where n is the number of words in the array and m is the maximum length among all strings.

For each word in words (n iterations), the algorithm iterates through each character of that word to create pairs of (s[i], s[-(i+1)]) using zip(s, reversed(s)). This pairing operation takes O(m) time for a word of length m. Within each character iteration, the trie operations (checking existence, creating nodes, and incrementing counters) are O(1). Therefore, the overall time complexity is O(n × m).

The space complexity is O(n × m). In the worst case, when all words have completely different prefix-suffix pairs, the trie needs to store a unique path for each word. Each word can contribute up to m nodes (one for each character position), and with n words, the maximum number of nodes in the trie is O(n × m). Each node stores a dictionary of children and a counter, but the space for these is already accounted for in the node count. The __slots__ optimization helps reduce memory overhead per node instance, but doesn't change the asymptotic complexity.

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

Common Pitfalls

1. Misunderstanding the Character Pairing Logic

Pitfall: Developers often misunderstand why we pair characters from the start and end of the string. They might think we need to check prefix and suffix separately, leading to incorrect implementations like:

# INCORRECT: Checking prefix and suffix separately def countPairs_wrong(words):  result = 0  for j in range(len(words)):  for i in range(j):  if words[j].startswith(words[i]) and words[j].endswith(words[i]):  result += 1  return result

Why it's wrong: While this brute force approach works, it defeats the purpose of using a Trie and has O(n²m) complexity.

Solution: Understand that the character pairing (s[i], s[len(s)-1-i]) simultaneously validates both conditions. When a string is both a prefix and suffix, these pairs will match perfectly.

2. Incorrect Order of Operations

Pitfall: Adding the count AFTER incrementing it, or incrementing before traversal:

# INCORRECT: Wrong order for char_pair in zip(word, reversed(word)):  if char_pair not in current_node.children:  current_node.children[char_pair] = TrieNode()  current_node = current_node.children[char_pair]  # Incrementing before accumulating - WRONG! current_node.count += 1 result += current_node.count # This includes the current word itself

Solution: Always accumulate the count BEFORE incrementing. The correct order is:

1. Traverse and accumulate existing counts
2. Only increment count after full traversal

3. Handling Edge Cases Incorrectly

Pitfall: Not considering that a word cannot be a prefix-suffix pair with itself:

# INCORRECT: Might count self-pairs if not careful if word in previous_words: # Wrong approach  result += 1

Solution: The algorithm naturally handles this by processing words in order and only counting previously inserted words (those with smaller indices).

4. Memory Inefficiency with Character Pairs

Pitfall: Storing character pairs inefficiently or creating unnecessary objects:

# INEFFICIENT: Creating new strings for pairs char_pair = word[i] + word[-(i+1)] # Creates new string objects

Solution: Use tuples for character pairs as they are immutable and hashable:

char_pair = (word[i], word[-(i+1)]) # Efficient tuple # Or better yet, use zip with reversed: for char_pair in zip(word, reversed(word)):

5. Forgetting to Initialize the Trie Root

Pitfall: Reusing the same root for multiple test cases or forgetting to initialize:

# INCORRECT: Using class variable (shared across instances) class Solution:  root = TrieNode() # This is shared!   def countPrefixSuffixPairs(self, words):  # Will have stale data from previous calls

Solution: Always create a fresh Trie root for each function call:

def countPrefixSuffixPairs(self, words):  root = TrieNode() # Fresh root for each call