Problem Description

Given a string s, you are to return the sum of counts of unique characters for all possible substrings of s.
A character is unique in a substring if it appears exactly once in that substring.
For example, in the substring "ABC", all characters are unique, but in "ABA", only 'B' is unique.

The task is: For every possible substring of s, count the number of unique characters and sum these counts.

• Constraints:
  • 1 <= s.length <= 10^4
  • s consists of uppercase English letters only.
• You must find an efficient solution that avoids brute-force enumeration of all substrings.

Thought Process

The brute-force approach would be to generate all possible substrings of s (which is O(N^2) substrings for length N), and for each substring, count the number of unique characters. However, this is far too slow for large N because counting unique characters in each substring is also O(N), making it O(N^3) overall.

To optimize, let's reverse the perspective: Instead of counting unique characters in every substring, consider each occurrence of a character and count in how many substrings it is unique. If we can compute this efficiently for each character, we can sum up these contributions for the answer.

The key insight is: For each occurrence of a character, we want to know in how many substrings it is the only occurrence of that character (i.e., it is unique in that substring).

Solution Approach

We solve the problem by tracking, for each character in s, the indices of its previous and next occurrence. This allows us to count, for each occurrence, how many substrings it is unique in.

• Step 1: For each character, maintain a list of all its occurrence indices in s.
• Step 2: For each occurrence at index i of character c:
  • Let prev be the index of the previous occurrence of c (-1 if none).
  • Let next be the index of the next occurrence of c (len(s) if none).
  • The number of substrings where s[i] is unique is (i - prev) * (next - i).
    • Why? The substring must start after prev and end before next, and must include i.
• Step 3: For all characters and all their occurrences, sum up these contributions.

This approach is efficient because it processes each character occurrence in constant time, resulting in an overall linear time solution.

Example Walkthrough

Let's use the example string "ABC":

• All substrings: "A", "B", "C", "AB", "BC", "ABC"
• Unique character counts:
  • "A": 1
  • "B": 1
  • "C": 1
  • "AB": 2
  • "BC": 2
  • "ABC": 3
• Sum: 1 + 1 + 1 + 2 + 2 + 3 = 10

Using the optimized approach:

• 'A' at index 0: prev = -1, next = none (so 3). Contribution = (0-(-1))*(3-0) = 1*3 = 3
• 'B' at index 1: prev = -1, next = none (so 3). Contribution = (1-(-1))*(3-1) = 2*2 = 4
• 'C' at index 2: prev = -1, next = none (so 3). Contribution = (2-(-1))*(3-2) = 3*1 = 3

Total = 3 + 4 + 3 = 10, which matches our earlier calculation.

Time and Space Complexity

• Brute-force approach:
  • Time: O(N^3) (O(N^2) substrings, O(N) per substring to count unique chars)
  • Space: O(1) extra (not counting output or substrings themselves)
• Optimized approach:
  • Time: O(N), because we only iterate through the string and each character's occurrences.
  • Space: O(N), for storing the occurrence indices of each character.

Summary

This problem is efficiently solved by shifting perspective: Instead of evaluating every substring, we count each character's contribution as a unique character across all substrings where it is unique. By leveraging previous and next occurrence indices, we can compute each contribution in constant time, resulting in a linear time solution. The key insight is to count "from the character's point of view" rather than "from the substring's point of view."

Code Implementation

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        index = {}
        for c in set(s):
            index[c] = [-1]
        for i, c in enumerate(s):
            index[c].append(i)
        for c in index:
            index[c].append(len(s))
        res = 0
        for c in index:
            arr = index[c]
            for i in range(1, len(arr) - 1):
                res += (arr[i] - arr[i-1]) * (arr[i+1] - arr[i])
        return res
      

class Solution {
public:
    int uniqueLetterString(string s) {
        vector<int> index[26];
        int n = s.size();
        for (int i = 0; i < 26; ++i) index[i].push_back(-1);
        for (int i = 0; i < n; ++i)
            index[s[i] - 'A'].push_back(i);
        for (int i = 0; i < 26; ++i) index[i].push_back(n);

        int res = 0;
        for (int c = 0; c < 26; ++c) {
            for (int i = 1; i < index[c].size() - 1; ++i) {
                res += (index[c][i] - index[c][i-1]) * (index[c][i+1] - index[c][i]);
            }
        }
        return res;
    }
};
      

class Solution {
    public int uniqueLetterString(String s) {
        List<Integer>[] index = new ArrayList[26];
        int n = s.length();
        for (int i = 0; i < 26; ++i) {
            index[i] = new ArrayList<>();
            index[i].add(-1);
        }
        for (int i = 0; i < n; ++i) {
            index[s.charAt(i) - 'A'].add(i);
        }
        for (int i = 0; i < 26; ++i) {
            index[i].add(n);
        }

        int res = 0;
        for (int c = 0; c < 26; ++c) {
            List<Integer> arr = index[c];
            for (int i = 1; i < arr.size() - 1; ++i) {
                res += (arr.get(i) - arr.get(i-1)) * (arr.get(i+1) - arr.get(i));
            }
        }
        return res;
    }
}
      

var uniqueLetterString = function(s) {
    const index = {};
    for (const c of new Set(s)) {
        index[c] = [-1];
    }
    for (let i = 0; i < s.length; ++i) {
        index[s[i]].push(i);
    }
    for (const c in index) {
        index[c].push(s.length);
    }
    let res = 0;
    for (const c in index) {
        const arr = index[c];
        for (let i = 1; i < arr.length - 1; ++i) {
            res += (arr[i] - arr[i-1]) * (arr[i+1] - arr[i]);
        }
    }
    return res;
};