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

1
2
3
4
5

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

1
2
3

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

Example 3

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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.