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

Total Appeal of A String

Number: 2340

Difficulty: Hard

Paid? No

Companies: Amazon, Microsoft

Problem Description

Given a string s, each substring’s appeal is defined as the number of distinct characters within it. The goal is to compute the total appeal for all possible contiguous substrings of s.

Key Insights

  • Brute force enumeration of all substrings is too slow given the constraints.
  • Rather than computing distinct counts for each substring independently, we can count each character’s contribution to the total appeal.
  • For every character at position i, its contribution to all substrings ending at i can be determined by the distance from its last occurrence.
  • Use a dynamic programming approach where we maintain a running sum of the appeals of substrings ending at each index.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string
Space Complexity: O(1) (using an array of fixed size 26 for tracking last occurrences)

Solution

The solution leverages the following idea: as you iterate through the string, track the last occurrence index for each character. For each position i, the additional appeal provided by the character s[i] is (i - lastOccurrence[s[i]]). This value represents how many new substrings ending at position i include s[i] as a new distinct character (since its previous occurrence). A running sum (currentAppeal) is maintained for substrings ending at each position, and the overall total is updated accordingly. This eliminates the need for explicit substring generation.

Code Solutions

# Python Code
def total_appeal(s: str) -> int:
    n = len(s)
    # Track last occurrence for each letter, initialize to -1 for a-z (26 characters)
    last_occurrence = [-1] * 26
    total = 0
    current_appeal = 0
    
    # Loop over each character in s
    for i, char in enumerate(s):
        char_index = ord(char) - ord('a')  # Map character to index 0-25
        # Each character adds i - last_occurrence for new substrings ending at i
        current_appeal += i - last_occurrence[char_index]
        last_occurrence[char_index] = i  # Update last occurrence of the letter
        total += current_appeal  # Add current appeal to total
    return total

# Example usage:
print(total_appeal("abbca"))  # Expected output: 28
← Back to All Questions