problemhardalgorithmsleetcode-828leetcode 828leetcode828

Count Unique Characters of All Substrings of a Given String

HardUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Let's define a function countUniqueChars(s) that returns the number of unique characters in s.

  • For example, calling countUniqueChars(s) if s = "LEETCODE" then "L", "T", "C", "O", "D" are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.

Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.

Notice that some substrings can be repeated so in this case you have to count the repeated ones too.

Examples

Example 1

Input: s = "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

Example 2

Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.

Example 3

Input: s = "LEETCODE"
Output: 92

Constraints

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

Solution

Method 1 – Contribution Technique (Index Tracking)

Intuition

Each character's contribution to the answer is determined by how many substrings it is unique in. For each occurrence of a character, we can find the distance to its previous and next occurrence, and the product of these distances gives the number of substrings where this character is unique.

Approach

  1. For each character, store the indices of its occurrences in the string (add -1 at the start and n at the end for boundaries).
  2. For each occurrence at index i, the number of substrings where it is unique is (i - prev) * (next - i), where prev and next are the previous and next occurrence indices.
  3. Sum up the contributions for all characters.

Code

C++
class Solution {
public:
    int uniqueLetterString(string s) {
        int n = s.size(), ans = 0;
        vector<vector<int>> pos(26, vector<int>{-1});
        for (int i = 0; i < n; ++i) pos[s[i] - 'A'].push_back(i);
        for (int c = 0; c < 26; ++c) pos[c].push_back(n);
        for (int c = 0; c < 26; ++c) {
            for (int i = 1; i < pos[c].size() - 1; ++i) {
                ans += (pos[c][i] - pos[c][i-1]) * (pos[c][i+1] - pos[c][i]);
            }
        }
        return ans;
    }
};
Go
func uniqueLetterString(s string) int {
    n := len(s)
    pos := make([][]int, 26)
    for i := range pos {
        pos[i] = []int{-1}
    }
    for i, c := range s {
        pos[c-'A'] = append(pos[c-'A'], i)
    }
    for i := range pos {
        pos[i] = append(pos[i], n)
    }
    ans := 0
    for _, p := range pos {
        for i := 1; i < len(p)-1; i++ {
            ans += (p[i] - p[i-1]) * (p[i+1] - p[i])
        }
    }
    return ans
}
Java
class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length(), ans = 0;
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; i++) pos[i] = new ArrayList<>();
        for (int i = 0; i < 26; i++) pos[i].add(-1);
        for (int i = 0; i < n; i++) pos[s.charAt(i) - 'A'].add(i);
        for (int i = 0; i < 26; i++) pos[i].add(n);
        for (int c = 0; c < 26; c++) {
            for (int i = 1; i < pos[c].size() - 1; i++) {
                ans += (pos[c].get(i) - pos[c].get(i-1)) * (pos[c].get(i+1) - pos[c].get(i));
            }
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun uniqueLetterString(s: String): Int {
        val n = s.length
        val pos = Array(26) { mutableListOf(-1) }
        for (i in s.indices) pos[s[i] - 'A'].add(i)
        for (p in pos) p.add(n)
        var ans = 0
        for (p in pos) {
            for (i in 1 until p.size-1) {
                ans += (p[i] - p[i-1]) * (p[i+1] - p[i])
            }
        }
        return ans
    }
}
Python
class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n = len(s)
        pos = {c: [-1] for c in set(s)}
        for i, ch in enumerate(s):
            pos.setdefault(ch, [-1]).append(i)
        for ch in pos:
            pos[ch].append(n)
        ans = 0
        for ch in pos:
            p = pos[ch]
            for i in range(1, len(p)-1):
                ans += (p[i] - p[i-1]) * (p[i+1] - p[i])
        return ans
Rust
impl Solution {
    pub fn unique_letter_string(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut pos = vec![vec![-1i32]; 26];
        for (i, &c) in s.iter().enumerate() {
            pos[(c - b'A') as usize].push(i as i32);
        }
        for p in pos.iter_mut() {
            p.push(n as i32);
        }
        let mut ans = 0;
        for p in pos.iter() {
            for i in 1..p.len()-1 {
                ans += (p[i] - p[i-1]) * (p[i+1] - p[i]);
            }
        }
        ans
    }
}
TypeScript
class Solution {
    uniqueLetterString(s: string): number {
        const n = s.length
        const pos: number[][] = Array.from({length: 26}, () => [-1])
        for (let i = 0; i < n; ++i) pos[s.charCodeAt(i) - 65].push(i)
        for (let i = 0; i < 26; ++i) pos[i].push(n)
        let ans = 0
        for (let c = 0; c < 26; ++c) {
            for (let i = 1; i < pos[c].length - 1; ++i) {
                ans += (pos[c][i] - pos[c][i-1]) * (pos[c][i+1] - pos[c][i])
            }
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string, as each character is processed a constant number of times.
  • 🧺 Space complexity: O(n) for storing positions.

Comments