Count Unique Characters of All Substrings of a Given String — Hard Problem & Solution

Problem statement

For a string t, let countUnique(t) be the number of characters that occur exactly once in t. For "CODE" that is 4; for "KAIRO" it is 5; for "AABB" it is 0.

Given s, return the sum of countUnique(t) over every substring t of s, modulo 10^9 + 7. Substrings at different positions count separately even when identical.

Example 1

Input: s = "ABC"
Output: 10
Explanation: Every one of the six substrings has all-unique characters: 1+1+1+2+2+3 = 10.

Example 2

Input: s = "ABA"
Output: 8
Explanation: The two A's cancel each other out in the substrings that contain both.

Example 3

Input: s = "KAIRO"
Output: 35

Constraints

• 1 <= s.length <= 100000
• s consists of uppercase English letters.

How to solve Count Unique Characters of All Substrings of a Given String

Reverse the order of summation. Instead of asking how many unique characters each substring has, ask how many substrings each occurrence is unique in — a quantity that depends only on its two neighbouring occurrences of the same letter.

Approach

1. For each letter keep last — the index of its most recent occurrence — and prev — the one before that, both starting at -1.
2. At index i with letter c, the occurrence at last[c] is now fully bracketed: it is unique in (last[c] - prev[c]) × (i - last[c]) substrings. Add that.
3. Shift prev[c] = last[c] and last[c] = i.
4. After the sweep, close out every letter's final occurrence using n as the right bracket.

Why it works

A substring s[l..r] counts the occurrence at p as unique exactly when prev < l <= p and p <= r < next. There are p - prev choices for l and next - p for r, and these ranges are independent — hence the product. Summing over all occurrences of all letters counts each (substring, unique character) pair exactly once.

Complexity

• Time — O(n)
• Space — O(26)

Pitfalls

• Enumerating substrings is O(n²) at best and cannot pass the stated limit.
• Forgetting the closing loop drops the contribution of every letter's last occurrence.
• The products reach about n²/4, which overflows 32 bits — accumulate in 64 bits before the modulo.

Reference solution

Python

def uniqueLetterString(s: str) -> int:
    MOD = 1000000007
    n = len(s)
    last = [-1] * 26
    prev = [-1] * 26
    total = 0
    for i, ch in enumerate(s):
        c = ord(ch) - 65
        total = (total + (i - last[c]) * (last[c] - prev[c])) % MOD
        prev[c] = last[c]
        last[c] = i
    for c in range(26):
        total = (total + (n - last[c]) * (last[c] - prev[c])) % MOD
    return total

JavaScript

var uniqueLetterString = function(s) {
    var MOD = 1000000007;
    var n = s.length;
    var last = [], prev = [];
    for (var t = 0; t < 26; t++) { last.push(-1); prev.push(-1); }
    var total = 0;
    for (var i = 0; i < n; i++) {
        var c = s.charCodeAt(i) - 65;
        total = (total + (i - last[c]) * (last[c] - prev[c])) % MOD;
        prev[c] = last[c];
        last[c] = i;
    }
    for (var d = 0; d < 26; d++) {
        total = (total + (n - last[d]) * (last[d] - prev[d])) % MOD;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Number of Ways to Separate Numbers Hard
• Form Largest Integer With Digits That Add up to Target Hard
• Restore the Array Hard
• Strange Printer Hard
• Special Binary String Hard
• Count Different Palindromic Subsequences Hard