Total Appeal of A String - Practice Coding Problems

Total Appeal of A String - Problem

The appeal of a string is the number of distinct characters found in the string.

For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.

Given a string s, return the total appeal of all of its substrings.

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

Input & Output

Example 1 — Basic Case

$ Input: s = "abbca"

› Output: 28

💡 Note: All substrings: "a"(1), "ab"(2), "abb"(2), "abbc"(3), "abbca"(3), "b"(1), "bb"(1), "bbc"(2), "bbca"(3), "b"(1), "bc"(2), "bca"(3), "c"(1), "ca"(2), "a"(1). Sum = 28

Example 2 — Single Character

$ Input: s = "z"

› Output: 1

💡 Note: Only one substring "z" with appeal 1

Example 3 — All Same

$ Input: s = "aaa"

› Output: 6

💡 Note: Substrings: "a"(1), "aa"(1), "aaa"(1), "a"(1), "aa"(1), "a"(1). Sum = 6

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with characters to analyze

Find All Substrings

Consider every contiguous subsequence

Sum Appeals

Add up distinct character counts

Key Takeaway

🎯 Key Insight: Calculate character contributions mathematically instead of generating all substrings

Asked in

G Google 15 F Facebook 12 a Amazon 8

The key insight is to calculate how each character contributes to all substrings rather than generating every substring. Best approach uses Dynamic Programming to track character positions and compute contributions mathematically. Time: O(n), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Set Reuse	O(n²)	O(k)	Generate substrings but reuse character tracking for better efficiency
Dynamic Programming	O(n)	O(k)	Track contribution of each character to all substrings ending at current position
Brute Force	O(n³)	O(k)	Generate all substrings and count distinct characters in each

Optimized with Set Reuse — Algorithm Steps

Step 1: For each starting position i, initialize empty set
Step 2: Extend substring from i to j, adding s[j] to set incrementally
Step 3: Add current set size to total appeal

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin with empty character set

Extend Right

Add new character to set, count current size

Accumulate

Add distinct count to running total

Code -

solution.c — C

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

long long solution(char* s) {
    long long total = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        bool seen[256] = {false};
        int distinct = 0;
        
        for (int j = i; j < n; j++) {
            if (!seen[(unsigned char)s[j]]) {
                seen[(unsigned char)s[j]] = true;
                distinct++;
            }
            total += distinct;
        }
    }
    
    return total;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops, each character processed once per starting position

⚠ Quadratic Growth

Space Complexity

O(k)

Set to store distinct characters, at most 26 for lowercase letters

✓ Linear Space

25.6K Views

Medium Frequency

~25 min Avg. Time

852 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

Optimized with Set Reuse — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler