Count Unique Characters of All Substrings: Contribution Counting

LeetCode 828 asks you to define a function countUniqueChars(s) that returns the number of unique characters in s (characters that appear exactly once), and then sum countUniqueChars(t) over every substring t of s. The brute-force approach enumerates all O(n^2) substrings and counts unique characters in each one, but that is far too slow for strings of length up to 10^5. The trick is to flip the perspective: instead of looking at substrings, look at each character and ask how many substrings it contributes to as a unique character.

The problem

Given a string s, define countUniqueChars(s) as the number of characters that appear exactly once in s. For example, countUniqueChars("LEETCODE") = 4 because L, T, O, D each appear once while E and C appear more than once.

Return the sum of countUniqueChars(t) for every substring t of s. Since the answer can be large, return it modulo 10^9 + 7.

Constraints:

• 1 <= s.length <= 10^5
• s consists of uppercase English letters only

The diagram above shows how each character in "ABCB" contributes to the total. Notice that the second B at index 3 has a much smaller contribution than the first B at index 1, because its left range is clamped by the earlier occurrence of the same character.

The key insight

Instead of iterating over all substrings, ask a different question: for a character at position i, how many substrings include s[i] as a unique character? A character is unique in a substring if and only if no other copy of that character appears in the same substring. So you need the substring to start after the previous occurrence of s[i] and end before the next occurrence.

Let prev be the last index where s[i] appeared before position i (or -1 if there is none), and let next be the first index where s[i] appears after position i (or n if there is none). The substring can start at any position from prev + 1 to i, giving (i - prev) choices. It can end at any position from i to next - 1, giving (next - i) choices. Multiplying these gives the total number of substrings where s[i] is unique: (i - prev) * (next - i).

Summing this over all positions gives the answer in O(n) time.

The solution

def unique_letter_string(s):
    n = len(s)
    prev = {}
    left = [0] * n
    right = [0] * n

    for i in range(n):
        if s[i] in prev:
            left[i] = i - prev[s[i]]
        else:
            left[i] = i + 1
        prev[s[i]] = i

    nxt = {}
    for i in range(n - 1, -1, -1):
        if s[i] in nxt:
            right[i] = nxt[s[i]] - i
        else:
            right[i] = n - i
        nxt[s[i]] = i

    return sum(left[i] * right[i] for i in range(n)) % (10**9 + 7)

The first pass builds left[i], the distance from index i to the previous occurrence of the same character (or to the imaginary position -1). The second pass builds right[i], the distance to the next occurrence (or to position n). The answer is the sum of all left[i] * right[i].

Visual walkthrough

Complexity analysis

The contribution counting approach reduces the problem from quadratic (or worse) to linear by eliminating the need to enumerate substrings entirely.

The building blocks

Contribution counting

The core technique here is contribution counting, sometimes called "contribution to the answer." Instead of aggregating over all substrings, you compute how much each element contributes to the global sum. This pattern appears in many problems where you sum a function over all subarrays or substrings. The key is to find, for each element, the number of subarrays or substrings where it participates in a specific way.

Other problems that use contribution counting include sum of subarray minimums (LeetCode 907), sum of subarray ranges (LeetCode 2104), and number of visible people in a queue. Whenever you see "sum over all subarrays/substrings of some per-element property," think contribution counting.

Previous and next occurrence tracking

The second building block is tracking the previous and next occurrence of the same character. This is a common pattern with hash maps. You make one left-to-right pass recording the last seen index for each character, and one right-to-left pass recording the next seen index. This gives you the boundaries you need for the contribution formula.

This same technique appears in problems involving duplicate elements in arrays, such as finding the number of distinct elements in each window, or computing subarray contributions bounded by repeated values.

Edge cases

Single character string. If s has length 1, the only substring is s itself, and the only character is unique. The answer is 1.

All characters the same. For a string like "AAAA", each A at index i has prev = i - 1 and next = i + 1 (with sentinels at -1 and n). Each A contributes exactly 1 * 1 = 1, so the total equals n. Every substring of length 1 contributes 1 unique character, and every longer substring contributes 0 because A is never unique in a multi-character substring of all A's.

All characters distinct. If every character is different, each character at index i has prev = -1 and next = n. Its contribution is (i + 1) * (n - i). The total is the sum of (i + 1)(n - i) for i from 0 to n-1, which equals n(n+1)(n+2)/6. Every character is unique in every substring that contains it.

Modular arithmetic. The problem asks for the result modulo 10^9 + 7. Since all contributions are positive and we only sum them, you can take the modulus at the end or accumulate modularly. No subtraction is involved, so there are no negative-modulus pitfalls.

From understanding to recall

You now understand why contribution counting transforms this problem from O(n^2) to O(n), and how the previous/next occurrence boundaries define each character's contribution. But recognizing this pattern quickly in an interview requires practice. The shift from "iterate over substrings" to "iterate over characters" is the kind of insight that feels obvious after you have seen it a few times, yet remains invisible when you have not.

Drilling this problem with spaced repetition helps you internalize the contribution counting template. Once the formula (i - prev) * (next - i) is automatic, you can apply it to a whole family of substring and subarray summation problems. Contribution counting is one of roughly 60 reusable building blocks in the CodeBricks system, and pairing it with previous/next occurrence tracking covers a significant slice of hard string problems.

Related posts

• Subarray Sum Equals K - Another problem where flipping the perspective from subarrays to prefix sums unlocks an efficient solution.
• Longest Substring Without Repeating Characters - Uses a sliding window to track character uniqueness across substrings.
• Distinct Subsequences - A different counting problem on strings, solved with 2D DP and the match/skip recurrence.

Contribution counting turns a hard substring problem into a clean linear scan. Once you see the pattern, you will reach for it whenever a problem asks you to sum a property across all substrings or subarrays.