We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Unique Characters of All Substrings of a Given String

Difficulty: Hard

Problem Description

Given a string s, return the sum of countUniqueChars(t) for all substrings t of s, where countUniqueChars(s) returns the number of unique characters in the string s.

Key Insights

  • A substring is defined as a contiguous sequence of characters within a string.
  • Unique characters in a substring can be efficiently counted using a hash table or similar data structure.
  • The contribution of each character to the count of unique characters can be determined by its position in the string and its occurrences.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case due to generating all substrings, but can be optimized. Space Complexity: O(1) if we consider only the input and some auxiliary variables, otherwise O(1) for the hash table storing character counts.

Solution

To solve this problem, we track the contribution of each character to the total count of unique characters across all substrings. We utilize a hash table to maintain the count of characters as we iterate through each possible starting index of the substring. For each character, we calculate how many substrings it contributes to as a unique character based on its last occurrence and update the total accordingly.

Code Solutions

def countUniqueChars(s):
    count = 0
    char_map = {}
    
    for i, char in enumerate(s):
        if char not in char_map:
            char_map[char] = 0
        char_map[char] += 1
    
    for char in char_map:
        if char_map[char] == 1:
            count += 1
            
    return count

def uniqueCharacterSubstrings(s):
    total_count = 0
    n = len(s)
    
    for i in range(n):
        char_map = {}
        unique_count = 0
        
        for j in range(i, n):
            if s[j] in char_map:
                char_map[s[j]] += 1
            else:
                char_map[s[j]] = 1
            
            if char_map[s[j]] == 1:  # first occurrence
                unique_count += 1
            elif char_map[s[j]] == 2:  # second occurrence
                unique_count -= 1
            
            total_count += unique_count
            
    return total_count

# Example usage:
print(uniqueCharacterSubstrings("ABC"))  # Output: 10
print(uniqueCharacterSubstrings("ABA"))  # Output: 8
print(uniqueCharacterSubstrings("LEETCODE"))  # Output: 92
← Back to All Questions