Abstract / Summary

Count the total number of unique characters across all possible substrings of a given string.

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 54% (100k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Hash Table
• String

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 computes the total contribution of each distinct character in a string to the count of substrings that contain that character exactly once. It does this by first recording every index where each character appears, then for each occurrence it calculates how many substrings treat that occurrence as the unique appearance of the character. The final sum of all such contributions yields the answer.

Key Steps

The algorithm can be broken down into a sequence of logical phases, each reflected by a concise code fragment.

Collecting character positions

seen = defaultdict(list)
for i, c in enumerate(s):
    seen[c].append(i)

During this pass the code builds a mapping from each character to a list of its indices in the original string. The use of defaultdict(list) eliminates the need for explicit existence checks, allowing the list to be extended directly.

Preparing sentinel boundaries

have = [-1] + seen[c] + [size]

For every character c, the list of its positions is padded with -1 at the front and size (the length of the string) at the end. These sentinel values simplify the handling of edge substrings that start before the first occurrence or end after the last occurrence.

Iterating over triples of consecutive positions

for prev, current, next in zip(have, have[1:], have[2:]):
    left  = current - prev
    right = next - current
    result += left * right

The zip construction walks through three aligned windows of the padded list: the previous index, the current index, and the next index. For each occurrence (current) the distance to the previous occurrence (left) and the distance to the next occurrence (right) are computed. Multiplying these distances gives the number of substrings where this particular occurrence is the sole appearance of the character. The product is accumulated into result.

Returning the accumulated total

return result

After all characters have been processed, the function returns the sum of contributions, which matches the required count of substrings with unique characters.

Edge Cases

The sentinel padding (-1 and size) ensures that characters appearing at the very beginning or end of the string are treated correctly. When a character occurs only once, the padded list becomes [-1, index, size]. The computed left equals index - (-1), i.e., index + 1, representing all possible start positions up to that character. The right equals size - index, representing all possible end positions from that character onward. Their product therefore counts every substring that includes the sole occurrence, which is precisely the expected contribution.

If the input string is empty, size is zero, the seen dictionary remains empty, and the outer loop over seen does not execute. Consequently, result stays at its initial value of zero, which is the correct answer for an empty input.

When a character repeats consecutively, such as "aa", the padded list for 'a' becomes [-1, 0, 1, 2]. The iteration over triples yields two contributions: one for the first 'a' with left = 1 and right = 1, and one for the second 'a' with the same values. Each contribution adds one, reflecting the two substrings "a" (at positions 0 and 1) that contain a unique 'a'. Substrings like "aa" are correctly excluded because neither occurrence is unique within that substring.

Performance Optimizations

The implementation avoids nested loops over the string length. By aggregating indices per character in a single pass and then processing each character’s list independently, the algorithm scales linearly with the total number of characters. The use of defaultdict(list) eliminates conditional checks during index collection, reducing overhead.

Padding each list with sentinel values removes the need for special-case logic when handling the first or last occurrence of a character. This uniform treatment allows the inner loop to use a simple zip over three slices, which is both concise and efficient in Python because it creates lightweight iterator objects rather than materializing intermediate lists.

Multiplication of the left and right distances directly yields the count of relevant substrings for a given occurrence, bypassing any explicit enumeration of substrings. This arithmetic shortcut eliminates combinatorial explosion and keeps the runtime proportional to the number of character occurrences rather than the number of possible substrings.

Imagine that the letters in the word are standing in a long line, and each letter wants to count the special spots where it is the only one of its kind. The computer looks at every letter one by one to see where it lives in that line. It keeps a secret notebook to remember every place each letter appears.

Once the notebook is full, a special math game begins for every type of letter. The computer looks at the current place of a letter and checks how far it is from the neighbor on the left and how far it is from the neighbor on the right. By multiplying those two distances together, the computer learns exactly how many different groups of letters can be made where that specific character stays all by itself. It adds all those little puzzle pieces together until every spot for every letter has been counted.

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

Time: linear
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	C++			Python			Java	TS
	WalkCCC	C++			Python			Java
	leetcode.ca	C++		Rust	Python	Go		Java	TS
	LeetcodeHelp	C++			Python			Java
	Progiez	C++			Python			Java
github	black-shadows	C++
	everthis		JS
	halfrost					Go
	JoshCrozier		JS
	lkwq007				Python
	lzl124631x	C++
	ruoru			Rust
	suxrobGM						C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
everthis	JavaScript
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
wisdompeak	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