Problem Description

You are given a 0-indexed array of strings called words.

The problem asks you to find pairs of strings where one string appears as both the beginning (prefix) and the ending (suffix) of another string.

Specifically, you need to:

1. Consider all pairs of indices (i, j) where i < j
2. Check if words[i] is both a prefix AND a suffix of words[j]
3. Count how many such pairs exist

For a string to be both a prefix and suffix of another string, it must:

• Start at the beginning of the target string (prefix condition)
• End at the end of the target string (suffix condition)

For example:

• "aba" is both a prefix and suffix of "ababa" because:
  • "ababa" starts with "aba" (prefix ✓)
  • "ababa" ends with "aba" (suffix ✓)
• "abc" is NOT both a prefix and suffix of "abcd" because:
  • "abcd" starts with "abc" (prefix ✓)
  • "abcd" does NOT end with "abc" (suffix ✗)

The solution uses a nested loop to check all valid pairs. For each word at index i, it checks all words at indices greater than i. It uses Python's startswith() and endswith() methods to verify if words[i] is both a prefix and suffix of words[j]. The expression t.endswith(s) and t.startswith(s) returns True (which equals 1) when both conditions are met, and False (which equals 0) otherwise, allowing direct addition to the answer counter.

Intuition

The key insight is that we need to check every possible pair where one string could potentially be both a prefix and suffix of another. Since we're looking for pairs (i, j) where i < j, we need to compare each string with all strings that come after it in the array.

The most straightforward approach is to check each pair directly. For any two strings, we can determine if one is both a prefix and suffix of the other by using built-in string operations. A string s is both a prefix and suffix of string t if and only if t starts with s AND t ends with s.

Why does this work? Consider that if a string appears at both the beginning and end of another string, these two occurrences might overlap (like "aba" in "ababa"), or they might be the same occurrence if the smaller string equals the larger string entirely. The beauty of using startswith() and endswith() is that they handle all these cases naturally without us having to worry about the overlap logic.

The brute force nature of checking all pairs is acceptable here because:

1. We must examine every valid pair at least once to determine if it satisfies our condition
2. The check for each pair (prefix and suffix verification) can be done efficiently using built-in string methods
3. There's no apparent pattern or property that would allow us to skip checking certain pairs without potentially missing valid answers

The solution leverages Python's boolean-to-integer conversion where True equals 1 and False equals 0, allowing us to directly add the result of our condition check to the running count.

Learn more about Trie patterns.

Solution Approach

The solution uses a nested loop enumeration approach to check all valid index pairs.

Implementation Steps:

1. Initialize Counter: Start with ans = 0 to keep track of valid pairs.

2. Outer Loop with Enumeration: Use enumerate(words) to iterate through each word along with its index i. This gives us the first element of each potential pair (i, j).

3. Inner Loop for Subsequent Elements: For each word at index i, iterate through all words that come after it using slice notation words[i + 1:]. This ensures we only check pairs where i < j.

4. Condition Check: For each pair (words[i], words[j]), check if words[i] is both a prefix and suffix of words[j]:

   • Use t.startswith(s) to check if s is a prefix of t
   • Use t.endswith(s) to check if s is a suffix of t
   • Combine both conditions with and operator

5. Count Valid Pairs: The expression t.endswith(s) and t.startswith(s) evaluates to either True (1) or False (0). Adding this directly to ans increments the counter when a valid pair is found.

Time Complexity: O(n² × m) where n is the number of words and m is the average length of the strings. We check n × (n-1) / 2 pairs, and each check takes O(m) time for the prefix/suffix comparison.

Space Complexity: O(1) as we only use a constant amount of extra space for the counter variable. The slice words[i + 1:] creates a view in Python 3, not a copy.

The elegance of this solution lies in its simplicity - it directly implements the problem's requirements without unnecessary complexity, using Python's built-in string methods that are optimized for these exact operations.

Example Walkthrough

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

Step 1: Initialize counter

• ans = 0

Step 2: Process i=0, s="a"

• Check against remaining words:
  • j=1: Is "a" both prefix and suffix of "aba"?
    • "aba".startswith("a") = True ✓
    • "aba".endswith("a") = True ✓
    • Both conditions met → ans = 0 + 1 = 1
  • j=2: Is "a" both prefix and suffix of "ababa"?
    • "ababa".startswith("a") = True ✓
    • "ababa".endswith("a") = True ✓
    • Both conditions met → ans = 1 + 1 = 2
  • j=3: Is "a" both prefix and suffix of "aa"?
    • "aa".startswith("a") = True ✓
    • "aa".endswith("a") = True ✓
    • Both conditions met → ans = 2 + 1 = 3

Step 3: Process i=1, s="aba"

• Check against remaining words:
  • j=2: Is "aba" both prefix and suffix of "ababa"?
    • "ababa".startswith("aba") = True ✓
    • "ababa".endswith("aba") = True ✓
    • Both conditions met → ans = 3 + 1 = 4
  • j=3: Is "aba" both prefix and suffix of "aa"?
    • "aa".startswith("aba") = False ✗
    • "aa".endswith("aba") = False ✗
    • Conditions not met → ans stays 4

Step 4: Process i=2, s="ababa"

• Check against remaining words:
  • j=3: Is "ababa" both prefix and suffix of "aa"?
    • "aa".startswith("ababa") = False ✗
    • "aa".endswith("ababa") = False ✗
    • Conditions not met → ans stays 4

Step 5: Process i=3, s="aa"

• No remaining words to check (i=3 is the last index)

Final Result: ans = 4

The valid pairs found were: (0,1), (0,2), (0,3), and (1,2), giving us a total count of 4.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 × m)

The algorithm uses two nested loops:

• The outer loop iterates through each word in the list, running n times where n is the length of words
• The inner loop iterates through all words after the current index, which in the worst case runs n-1, n-2, ..., 1 times respectively
• This gives us n × (n-1) / 2 iterations total, which is O(n^2)
• For each pair of words (s, t), we perform two string operations:
  • t.endswith(s): This takes O(m) time where m is the maximum length of the strings
  • t.startswith(s): This also takes O(m) time
• Therefore, the overall time complexity is O(n^2 × m)

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• The variable ans to store the count
• The loop variables i, s, and t which are references to existing strings
• No additional data structures are created
• The slicing operation words[i + 1:] creates a view/iterator that doesn't copy the actual strings

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

Common Pitfalls

1. Overlooking the Special Case Where Prefix Equals the Entire String

A common misconception is thinking that a string cannot be both a prefix and suffix of another string if they have the same length. However, when words[i] equals words[j], it is technically both a prefix and suffix of itself.

Example:

• If words = ["abc", "abc"], then "abc" is both a prefix and suffix of "abc" at index 1
• This should count as a valid pair (0, 1)

Solution: The current implementation handles this correctly since startswith() and endswith() return True when the strings are identical. No special handling needed.

2. Incorrect Index Handling in Inner Loop

A frequent mistake is using range(i, len(words)) or range(i+1, len(words)) with indexing like words[j] but forgetting to properly reference the index j.

Incorrect Implementation:

for i in range(len(words)):
    for j in range(i + 1, len(words)):
        # Forgot to use words[j], used words[i+1:] instead
        for t in words[i + 1:]:  # Wrong! This creates nested iteration
            count += t.startswith(words[i]) and t.endswith(words[i])

Solution: Either use index-based iteration consistently or use the slice approach as shown in the correct solution. The slice words[i + 1:] automatically handles the "all words after index i" requirement.

3. Performance Degradation with Repeated String Operations

Some developers might try to optimize by caching or pre-processing, but this can actually hurt performance for this problem:

Inefficient Attempt:

# Trying to be "clever" by pre-computing all prefixes/suffixes
for i, s in enumerate(words):
    prefixes = [words[j][:len(s)] for j in range(i+1, len(words))]
    suffixes = [words[j][-len(s):] for j in range(i+1, len(words))]
    # This creates unnecessary string slices and lists

Solution: Stick with the built-in startswith() and endswith() methods. They're optimized at the C level and avoid creating intermediate strings. They also handle edge cases like when the prefix/suffix is longer than the target string.

4. Misunderstanding the Direction of Comparison

A critical error is checking if words[j] is a prefix/suffix of words[i] instead of the reverse.

Wrong Direction:

for i, s in enumerate(words):
    for t in words[i + 1:]:
        # Wrong! Checking if t is prefix/suffix of s
        count += s.startswith(t) and s.endswith(t)

Solution: Remember that we're checking if words[i] (the earlier word) is a prefix/suffix of words[j] (the later word). The correct check is words[j].startswith(words[i]).