Abstract / Summary

Count how many index pairs have the same prefix and suffix strings in a list of words

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 78% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Function
• Rolling Hash
• String
• String Matching
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method countPrefixSuffixPairs. The method receives a list of strings and returns the number of unordered pairs (i, j) where the string at index j both starts with and ends with the string at index i. The algorithm iterates over all possible pairs using a double-loop and leverages Python’s built-in string methods to perform the prefix and suffix checks.

Key Steps

Initialization

The method begins by creating a counter result set to zero and storing the length of the input list in size.

result = 0
size = len(words)

Pair Generation

Two nested for loops generate every ordered pair where the second index is greater than the first, guaranteeing that each unordered pair is examined exactly once.

for i in range(size):
    for j in range(i + 1, size):
        ...

Prefix-and-Suffix Test

Inside the inner loop the expression

words[j].startswith(words[i]) and words[j].endswith(words[i])

evaluates to a Boolean value. In Python, True is equivalent to 1 and False to 0. Adding this Boolean directly to result increments the counter only when both conditions hold.

result += words[j].startswith(words[i]) and words[j].endswith(words[i])

Return

After all pairs have been examined, the accumulated count is returned.

return result

Edge Cases Handled

When the input list is empty or contains a single element, size becomes 0 or 1. The outer loop runs zero times, so the method returns 0 without entering the inner loop.

If any string in the list is empty (""), the startswith and endswith checks treat the empty string as a universal prefix and suffix. Consequently, every other string will satisfy both conditions with the empty string, and the algorithm correctly counts those pairs.

When two strings are identical, the inner loop still treats them as distinct indices (i < j). Since a string trivially starts and ends with itself, the pair contributes 1 to the result, matching the intended definition of a pair of different positions.

The code also gracefully handles strings where the prefix and suffix overlap (e.g., "aba" with "a"). The built-in methods correctly identify both the start and end positions, so the pair is counted when appropriate.

Performance Optimizations Observed

The implementation relies on Python’s highly optimized C-level string methods startswith and endswith. These functions perform early termination as soon as a mismatch is found, avoiding unnecessary character comparisons for long strings that differ early.

By storing len(words) in the local variable size, the code prevents repeated attribute lookups inside the loop, reducing overhead.

The use of the Boolean-to-integer conversion in the statement result += condition eliminates an explicit if block, allowing the interpreter to execute a single addition operation per pair. This micro-optimization reduces branch misprediction costs in tight loops.

Finally, the double-loop iterates only over pairs where j > i, halving the number of comparisons relative to a naïve double iteration over all ordered pairs. This ensures that each unordered pair is considered exactly once, cutting the total work in half.

Imagine you have a big basket full of word cards. This code looks at every single pair of cards in that basket to see if they fit together in a special way.

First, the code picks one card from the basket. Then, it looks at every other card that comes after the first one. It checks two things. It looks to see if the second card starts with the same letters as the first card. Then it also looks to see if that same second card ends with those exact same letters too.

If a pair of cards fits both of those rules, a counter goes up by one. The code keeps doing this for every possible pair in the basket until it has checked all of them. Each time it finds a matching pair, the counter gets bigger, keeping track of how many pairs act like twins in that special way.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++			Python	TS
	WalkCCC		Java	C++			Python
	leetcode.ca		Java	C++		Go	Python	TS
	Progiez		Java	C++			Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	Shamik07				Dart
	varunu28		Java
	withaarzoo			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
Shamik07	Dart
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality