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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Unique Characters of All Substrings of a Given String

Number: 855

Difficulty: Hard

Paid? No

Companies: Amazon, Microsoft, ForUsAll

Problem Description

Given an uppercase English string s, compute the sum of unique characters count across all of its substrings. For a substring t, countUniqueChars(t) returns the number of characters which appear exactly once in t. Note that even if some substrings are identical, they are considered separately in the sum.

Key Insights

  • Instead of evaluating each substring (which is too slow for s.length up to 10^5), compute the contribution of each character to the final answer.
  • For every occurrence of character c at index i, determine the number of substrings where this occurrence is the unique instance of c.
  • Use the idea of "contribution":
    • Let prev be the index of the previous occurrence of the same character (or -1 if none).
    • Let next be the index of the next occurrence of the same character (or s.length if none).
    • Then, the number of substrings that include s[i] as the only occurrence of that character is (i - prev) * (next - i).
  • Sum these contributions for all characters in s.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution uses a mathematical insight. Iterate through the string while tracking the previous and next occurrence indexes for each character. For every occurrence at index i, calculate its contribution by finding the distance to the previous occurrence and the distance to the next occurrence. Multiply these two distances to determine in how many substrings s[i] can be the unique instance of that character and sum the results. This eliminates the need to generate all substrings explicitly.

Code Solutions

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n = len(s)
        # Initialize dictionaries to hold the last seen index and next seen index for each character.
        prev_index = {ch: -1 for ch in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"}
        next_index = {ch: n for ch in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"}
        
        # Create list to store previous occurrence index for each position.
        prev_occurrence = [-1] * n
        for i in range(n):
            ch = s[i]
            prev_occurrence[i] = prev_index[ch]
            prev_index[ch] = i
        
        # Create list to store next occurrence index for each position.
        next_occurrence = [n] * n
        # Reset dictionary for next occurrence.
        next_index = {ch: n for ch in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"}
        for i in range(n - 1, -1, -1):
            ch = s[i]
            next_occurrence[i] = next_index[ch]
            next_index[ch] = i
        
        result = 0
        # Calculate contribution for every position in s.
        for i in range(n):
            left = i - prev_occurrence[i]
            right = next_occurrence[i] - i
            result += left * right
        return result

# Example usage:
# solution = Solution()
# print(solution.uniqueLetterString("ABC"))  # Output: 10
← Back to All Questions