LeetCode Problem 3042

Difficulty: 🟢 Easy
Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function

Solution

LeetCode 3042 - Count Prefix and Suffix Pairs I

Problem Understanding

The problem gives us an array of strings called words. For every pair of indices (i, j) where i < j, we must determine whether words[i] is both a prefix and a suffix of words[j].

A string is a prefix of another string if it appears at the beginning. A string is a suffix if it appears at the end.

For example:

• "aba" is a prefix of "ababa" because "ababa" starts with "aba".
• "aba" is also a suffix of "ababa" because "ababa" ends with "aba".
• Therefore, "aba" satisfies both conditions for "ababa".

Our task is to count how many index pairs satisfy this property.

The input consists of:

• An array words
• Each element is a lowercase English string
• We must consider every pair (i, j) such that i < j

The output is a single integer representing the number of valid pairs.

The constraints are very small:

• 1 <= words.length <= 50
• 1 <= words[i].length <= 10

These constraints are important because they tell us that even a straightforward comparison of every pair of strings is completely feasible. There are at most:

• 50 × 49 / 2 = 1225 pairs
• Each string has length at most 10

This means a simple solution will easily run within limits.

Some important edge cases include:

• Strings that are exactly equal, since a string is always both a prefix and suffix of itself.
• Single-character strings.
• Cases where the candidate prefix is longer than the target string.
• Arrays containing only one word, which produce zero valid pairs.
• Repeated strings appearing multiple times at different indices.

Approaches

Brute Force Approach

The most direct solution is to examine every pair (i, j) where i < j.

For each pair:

1. Let a = words[i].
2. Let b = words[j].
3. Check whether b starts with a.
4. Check whether b ends with a.
5. If both conditions are true, increment the answer.

This approach is correct because the problem definition directly asks us to evaluate every valid index pair. By checking all pairs and counting exactly those that satisfy the condition, we obtain the correct result.

The time complexity is acceptable because there are at most 1225 pairs and each string comparison involves at most 10 characters.

Optimal Approach

Because the constraints are extremely small, there is no need for a more sophisticated structure such as a Trie, rolling hash, or advanced string matching algorithm.

The key observation is that Python and Go already provide efficient operations for checking prefixes and suffixes. Since string lengths are at most 10, each check is effectively constant time.

Therefore, the optimal solution is simply:

• Enumerate all pairs (i, j)
• Use prefix and suffix checks
• Count the valid pairs

This solution is both simple and optimal for the given constraints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² · m)	O(1)	Check every pair and compare characters manually
Optimal	O(n² · m)	O(1)	Check every pair using built-in prefix/suffix operations

Here:

• n is the number of words.
• m is the maximum word length.

Since m ≤ 10, the practical runtime is extremely small.

Algorithm Walkthrough

1. Initialize a variable count to 0.
2. Iterate through all possible first indices i from 0 to n - 1.
3. For each i, iterate through all indices j such that j > i.
4. Let:

• prefixSuffix = words[i]
• target = words[j]

5. Check whether target starts with prefixSuffix.
6. Check whether target ends with prefixSuffix.
7. If both checks return true, increment count.
8. After all pairs have been processed, return count.

Why it works

The algorithm explicitly evaluates every pair (i, j) with i < j, which are exactly the pairs defined in the problem statement. For each pair, it verifies the required property that words[i] is both a prefix and a suffix of words[j]. Since every valid pair is counted exactly once and every invalid pair is ignored, the final count is correct.

Python Solution

from typing import List

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        count = 0
        n = len(words)

        for i in range(n):
            for j in range(i + 1, n):
                if words[j].startswith(words[i]) and words[j].endswith(words[i]):
                    count += 1

        return count

The implementation follows the algorithm directly.

The variable count stores the number of valid pairs found so far. The nested loops generate every pair (i, j) with i < j. For each pair, the built-in methods startswith() and endswith() determine whether words[i] is simultaneously a prefix and suffix of words[j].

Whenever both conditions are satisfied, the answer is incremented. After all pairs are processed, the result is returned.

Go Solution

func countPrefixSuffixPairs(words []string) int {
	count := 0
	n := len(words)

	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if len(words[i]) <= len(words[j]) &&
				words[j][:len(words[i])] == words[i] &&
				words[j][len(words[j])-len(words[i]):] == words[i] {
				count++
			}
		}
	}

	return count
}

The Go version performs the same logic. Since Go does not provide built-in StartsWith and EndsWith methods on strings directly, we compare slices of the string.

Before slicing, we verify that words[i] is not longer than words[j]. This prevents invalid slice operations and correctly handles cases where a longer string cannot possibly be a prefix or suffix of a shorter one.

Worked Examples

Example 1

words = ["a","aba","ababa","aa"]

Initial state:

Pair	Prefix/Suffix Candidate	Target	Valid?
(0,1)	"a"	"aba"	Yes
(0,2)	"a"	"ababa"	Yes
(0,3)	"a"	"aa"	Yes
(1,2)	"aba"	"ababa"	Yes
(1,3)	"aba"	"aa"	No
(2,3)	"ababa"	"aa"	No

Running count:

Pair Processed	Count
(0,1)	1
(0,2)	2
(0,3)	3
(1,2)	4
(1,3)	4
(2,3)	4

Final answer:

4

Example 2

words = ["pa","papa","ma","mama"]

Pair	Candidate	Target	Valid?
(0,1)	"pa"	"papa"	Yes
(0,2)	"pa"	"ma"	No
(0,3)	"pa"	"mama"	No
(1,2)	"papa"	"ma"	No
(1,3)	"papa"	"mama"	No
(2,3)	"ma"	"mama"	Yes

Final count:

2

Example 3

words = ["abab","ab"]

Pair	Candidate	Target	Valid?
(0,1)	"abab"	"ab"	No

The candidate string is longer than the target string, so it cannot be both a prefix and a suffix.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² · m)	Every pair is checked, each check examines up to m characters
Space	O(1)	Only a few variables are used

The nested loops generate all O(n²) pairs. For each pair, the prefix and suffix checks may inspect up to m characters. Since m ≤ 10, the runtime is very small in practice. No auxiliary data structures proportional to input size are used, so the space complexity remains constant.

Test Cases

from typing import List

s = Solution()

assert s.countPrefixSuffixPairs(["a", "aba", "ababa", "aa"]) == 4  # Example 1
assert s.countPrefixSuffixPairs(["pa", "papa", "ma", "mama"]) == 2  # Example 2
assert s.countPrefixSuffixPairs(["abab", "ab"]) == 0  # Example 3

assert s.countPrefixSuffixPairs(["a"]) == 0  # Single element
assert s.countPrefixSuffixPairs(["a", "a"]) == 1  # Equal strings
assert s.countPrefixSuffixPairs(["abc", "abc"]) == 1  # Exact match
assert s.countPrefixSuffixPairs(["ab", "abab"]) == 1  # Prefix and suffix
assert s.countPrefixSuffixPairs(["ab", "abcd"]) == 0  # Prefix only
assert s.countPrefixSuffixPairs(["cd", "abcd"]) == 0  # Suffix only
assert s.countPrefixSuffixPairs(["x", "xx", "xxx"]) == 3  # Multiple valid pairs
assert s.countPrefixSuffixPairs(["abc", "def", "ghi"]) == 0  # No matches
assert s.countPrefixSuffixPairs(["aa", "aaaa", "aaaaaa"]) == 3  # Repeated pattern
assert s.countPrefixSuffixPairs(["a", "b", "a"]) == 0  # Ordering matters
assert s.countPrefixSuffixPairs(["z", "zz", "zzz", "zzzz"]) == 6  # Every pair valid

Test Summary

Test	Why
["a","aba","ababa","aa"]	Official example
["pa","papa","ma","mama"]	Official example
["abab","ab"]	Candidate longer than target
["a"]	Minimum array size
["a","a"]	Equal strings
["abc","abc"]	Full string match
["ab","abab"]	Valid prefix and suffix
["ab","abcd"]	Prefix only
["cd","abcd"]	Suffix only
["x","xx","xxx"]	Multiple overlapping matches
["abc","def","ghi"]	No valid pairs
["aa","aaaa","aaaaaa"]	Repeated pattern strings
["a","b","a"]	Verifies index ordering
["z","zz","zzz","zzzz"]	Dense valid-pair scenario

Edge Cases

A Candidate String Longer Than the Target

A string cannot be a prefix or suffix of a shorter string if its length exceeds the target's length. For example, "abab" cannot be a prefix or suffix of "ab". This can easily cause bugs in implementations that perform slicing without checking lengths first. The Go solution explicitly verifies the length condition before slicing, while Python's built-in methods naturally return False.

Identical Strings

If two strings are exactly the same, then one is both a prefix and a suffix of the other. For example, "abc" and "abc" form a valid pair. Some implementations mistakenly require the second string to be strictly longer. The presented solution correctly counts identical strings because both prefix and suffix checks succeed.

Single-Element Arrays

When words contains only one string, there are no pairs (i, j) satisfying i < j. The answer must therefore be 0. The nested loops naturally handle this case because the inner loop never executes.

Repeated Characters and Overlapping Patterns

Strings such as "a", "aa", "aaa", and "aaaa" create many valid prefix-suffix relationships. These cases often expose logic errors where only prefixes or only suffixes are checked. The implementation independently verifies both conditions, ensuring that overlapping and repetitive patterns are counted correctly.

Prefix Without Suffix, or Suffix Without Prefix

A common mistake is checking only one side. For example:

• "ab" is a prefix of "abcd" but not a suffix.
• "cd" is a suffix of "abcd" but not a prefix.

The solution requires both conditions to be true simultaneously, which exactly matches the problem definition.