828. Count Unique Characters of All Substrings of a Given String

Problem Description

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. Test cases are generated such that the answer fits in a 32-bit integer.

A substring is a contiguous sequence of characters within a string.

Examples:

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

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

Input: s = "LEETCODE"
Output: 92

Constraints:

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

Python Solution

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        last = {}  # last two positions of each char
        for c in set(s):
            last[c] = [-1, -1]
            
        result = 0
        for i, c in enumerate(s):
            prev, pprev = last[c]
            result += (i - prev) * (prev - pprev)
            last[c] = [i, prev]
            
        # Handle the last contribution
        for c in last:
            prev, pprev = last[c]
            result += (len(s) - prev) * (prev - pprev)
            
        return result

Implementation Notes:

• Uses dynamic programming approach
• Tracks last two positions of each character
• Time complexity: O(n)
• Space complexity: O(1) since only uppercase letters

Java Solution

class Solution {
    public int uniqueLetterString(String s) {
        int[][] last = new int[26][2];
        for (int i = 0; i < 26; i++) {
            last[i][0] = last[i][1] = -1;
        }
        
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'A';
            result += (i - last[c][1]) * (last[c][1] - last[c][0]);
            last[c][0] = last[c][1];
            last[c][1] = i;
        }
        
        // Handle the last contribution
        for (int i = 0; i < 26; i++) {
            result += (s.length() - last[i][1]) * (last[i][1] - last[i][0]);
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    int uniqueLetterString(string s) {
        vector> last(26, vector(2, -1));
        
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int c = s[i] - 'A';
            result += (i - last[c][1]) * (last[c][1] - last[c][0]);
            last[c][0] = last[c][1];
            last[c][1] = i;
        }
        
        // Handle the last contribution
        for (int i = 0; i < 26; i++) {
            result += (s.length() - last[i][1]) * (last[i][1] - last[i][0]);
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {string} s
 * @return {number}
 */
var uniqueLetterString = function(s) {
    const last = new Map();
    
    // Initialize last positions for each character
    for (const c of new Set(s)) {
        last.set(c, [-1, -1]);
    }
    
    let result = 0;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        const [pprev, prev] = last.get(c);
        result += (i - prev) * (prev - pprev);
        last.set(c, [prev, i]);
    }
    
    // Handle the last contribution
    for (const [c, [pprev, prev]] of last) {
        result += (s.length - prev) * (prev - pprev);
    }
    
    return result;
};

C# Solution

public class Solution {
    public int UniqueLetterString(string s) {
        var last = new Dictionary();
        
        // Initialize last positions for each character
        foreach (char c in s.Distinct()) {
            last[c] = new int[] { -1, -1 };
        }
        
        int result = 0;
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            int prev = last[c][1], pprev = last[c][0];
            result += (i - prev) * (prev - pprev);
            last[c] = new int[] { prev, i };
        }
        
        // Handle the last contribution
        foreach (var kvp in last) {
            int prev = kvp.Value[1], pprev = kvp.Value[0];
            result += (s.Length - prev) * (prev - pprev);
        }
        
        return result;
    }
}

Implementation Notes:

• Uses dictionary to track character positions
• Calculates contribution of each character
• Time complexity: O(n)
• Space complexity: O(1)