Count Unique Characters of All Substrings of a Given String

Hard
657.

Count Unique Characters of All Substrings of a Given String

Count Unique Characters of All Substrings of a Given String is a hard coding problem on strings, hash table and counting, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var uniqueLetterString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Unique Characters of All Substrings of a Given String Solution

Count Unique Characters of All Substrings of a Given String solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Unique Characters of All Substrings of a Given String is a hard coding problem on strings, hash table and counting, asked in Amazon, Google and Meta interviews.

  • Difficulty: Hard
  • Topics: Strings, Hash Table, Counting
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Count Unique Characters of All Substrings of a Given String

  1. Hint 1

    Summing over substrings is hopeless directly. Flip it: count the contribution of each occurrence of each character.

  2. Hint 2

    An occurrence at index i is unique in exactly the substrings that contain it but not the previous or next occurrence of the same character.

  3. Hint 3

    If prev and next are those neighbouring positions, the count of such substrings is (i - prev) × (next - i).

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

Java

public static int uniqueLetterString(String s) {
    final long MOD = 1000000007L;
    int n = s.length();
    int[] last = new int[26];
    int[] prev = new int[26];
    Arrays.fill(last, -1);
    Arrays.fill(prev, -1);
    long total = 0;
    for (int i = 0; i < n; i++) {
        int c = s.charAt(i) - 'A';
        total = (total + (long) (i - last[c]) * (last[c] - prev[c])) % MOD;
        prev[c] = last[c];
        last[c] = i;
    }
    for (int c = 0; c < 26; c++) {
        total = (total + (long) (n - last[c]) * (last[c] - prev[c])) % MOD;
    }
    return (int) total;
}

C++

int uniqueLetterString(string s) {
    const long long MOD = 1000000007LL;
    int n = (int) s.size();
    vector<int> last(26, -1), prev(26, -1);
    long long total = 0;
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'A';
        total = (total + (long long) (i - last[c]) * (last[c] - prev[c])) % MOD;
        prev[c] = last[c];
        last[c] = i;
    }
    for (int c = 0; c < 26; c++) {
        total = (total + (long long) (n - last[c]) * (last[c] - prev[c])) % MOD;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets