Count Unique Characters of All Substrings of a Given String

Count Unique Characters of All Substrings of a Given String - 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.

Notice that some substrings can be repeated so in this case you have to count the repeated ones too.

Input & Output

Example 1 — Basic Case

$ Input: s = "ABC"

› Output: 10

💡 Note: Substrings: "A"(1), "B"(1), "C"(1), "AB"(2), "BC"(2), "ABC"(3). Sum: 1+1+1+2+2+3 = 10

Example 2 — Repeated Characters

$ Input: s = "ABA"

› Output: 8

💡 Note: Substrings: "A"(1), "B"(1), "A"(1), "AB"(2), "BA"(2), "ABA"(1). Sum: 1+1+1+2+2+1 = 8

Example 3 — Single Character

$ Input: s = "A"

› Output: 1

💡 Note: Only one substring "A" with 1 unique character. Sum: 1

Constraints

1 ≤ s.length ≤ 10⁴
s consists of uppercase English letters only.

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with characters at positions

Generate Substrings

All possible contiguous substrings

Count & Sum

Count unique chars in each substring and sum

Key Takeaway

🎯 Key Insight: Calculate each character's contribution to all substrings instead of checking every substring individually

Asked in

G Google 25 a Amazon 18 f Facebook 12

The key insight is to calculate each character's contribution across all substrings rather than examining each substring individually. Best approach uses contribution-based calculation in O(n) time by finding boundaries where each character remains unique. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Contribution-Based Approach	O(n)	O(1)	Calculate each character's contribution to all substrings where it appears uniquely
Brute Force - Check All Substrings	O(n³)	O(1)	Generate all substrings and count unique characters in each

Contribution-Based Approach — Algorithm Steps

For each character position, find previous and next occurrence of same character
Calculate number of substrings where this character is unique
Sum contributions of all character positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Boundaries

For each character, find previous and next occurrence of same character

Calculate Range

Determine range of substrings where character is unique

Sum Contributions

Add up all individual character contributions

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    int total = 0;
    
    // For each character position, calculate its contribution
    for (int i = 0; i < n; i++) {
        char ch = s[i];
        
        // Find previous occurrence of same character
        int left = -1;
        for (int j = i - 1; j >= 0; j--) {
            if (s[j] == ch) {
                left = j;
                break;
            }
        }
        
        // Find next occurrence of same character
        int right = n;
        for (int j = i + 1; j < n; j++) {
            if (s[j] == ch) {
                right = j;
                break;
            }
        }
        
        // Calculate contribution
        int contribution = (i - left) * (right - i);
        total += contribution;
    }
    
    return total;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string, each character processed once with constant time operations

✓ Linear Growth

Space Complexity

O(1)

Only storing last seen positions of characters (at most 26 for English letters)

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Contribution-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler