Total Appeal of A String

#1709 Most AskedHard

Total Appeal of A String #1709 Most Asked

Hard

Google

5 views

Topics:

Strings

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.

Example 1:

Input: s = "abbca"
Output: 28
Explanation: The following are the substrings of "abbca":
- Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
- Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
- Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7.
- Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 5: "abbca" has an appeal of 3. The sum is 3.
The total sum is 5 + 7 + 7 + 6 + 3 = 28.

Example 2:

Input: s = "code"
Output: 20
Explanation: The following are the substrings of "code":
- Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
- Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6.
- Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 4: "code" has an appeal of 4. The sum is 4.
The total sum is 4 + 6 + 6 + 4 = 20.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string?
Does the string contain only lowercase English letters, or can it contain uppercase letters, numbers, or special characters?
Are we concerned about integer overflow when calculating the total appeal?
Is the 'appeal' of a substring simply the number of unique characters it contains, or is there a more complex definition of 'appeal'?
If the input string is empty, what should be the return value?

Brute Force Solution

Approach

To find the total appeal, we will look at every possible section of the given string. For each section we find, we'll calculate how appealing it is and add that to our total appeal.

Here's how the algorithm would work step-by-step:

Consider all the sections that start at the very beginning of the string.
Calculate the appeal of each of those sections and add it to a running total.
Now, consider all the sections that start at the second letter of the string.
Calculate the appeal of each of these new sections and add it to the running total.
Keep doing this, each time starting at the next letter of the string, until you have considered sections starting at the very last letter.
The final running total you have is the total appeal of the string.

Code Implementation

def total_appeal_brute_force(input_string):
    string_length = len(input_string)
    total_appeal = 0

    # Iterate through all possible starting positions
    for starting_index in range(string_length):

        # For each starting position, iterate through all possible ending positions
        for ending_index in range(starting_index, string_length):
            substring = input_string[starting_index:ending_index + 1]

            # Calculate appeal of the substring: unique chars
            unique_characters = set(substring)
            substring_appeal = len(unique_characters)

            # Add the substring's appeal to the total
            total_appeal += substring_appeal

    return total_appeal

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the string of length n, considering substrings starting at each index. For each starting index, it iterates to the end of the string to define all substrings starting at that index. Therefore, the outer loop runs n times, and the inner loop’s average runtime can be approximated as n/2. The total operations performed is therefore roughly proportional to n * n/2, which simplifies to O(n²).

Space Complexity

O(1) – The described algorithm iterates through all possible substrings of the input string, but it doesn't explicitly create any auxiliary data structures (like lists, arrays, or hash maps) to store intermediate results or track visited locations. The appeal calculation and summation appear to happen in place, using only a few constant-sized variables for indexing and accumulation. Therefore, the space used beyond the input string itself remains constant, regardless of the string's length, N. This leads to a space complexity of O(1).

Optimal Solution

Approach

The goal is to find the total appeal of a string by considering all its substrings. Instead of generating every single substring, which would be slow, we use a clever trick to count how many times each character appears in all possible substrings.

Here's how the algorithm would work step-by-step:

Consider each character in the string one at a time.
For each character, figure out how many substrings contain that specific character.
To do this, look at the position of the character in the string.
Multiply the position of the character (plus one) by how many characters are left in the string after it (including itself). This tells you the number of substrings that include that specific character.
Do this for every character in the string and add up all the results.
The final sum is the total appeal of the string.

Code Implementation

def total_appeal_of_a_string(input_string):
    string_length = len(input_string)
    total_appeal = 0

    for index in range(string_length):
        # Each char's contribution is based on its position
        substrings_with_char = (index + 1) * (string_length - index)

        # Add to the total appeal count.
        total_appeal += substrings_with_char

    return total_appeal

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once, examining each character's position. For each character, a constant number of arithmetic operations (multiplication and addition) are performed to calculate its contribution to the total appeal. Since the number of operations per character is constant, and the loop iterates 'n' times where 'n' is the length of the string, the overall time complexity is directly proportional to the input size. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm iterates through the string, calculating the contribution of each character to the total appeal. It only uses a few constant space variables to store the current character's position and the running total appeal. No auxiliary data structures that scale with the input size N (the length of the string) are employed. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty String	Return 0 as an empty string has no appeal.
Null String	Throw IllegalArgumentException or return 0, depending on specification.
String with only one character	Return 1 as the only substring is the character itself.
String with all identical characters (e.g., 'aaaa')	The number of substrings is n*(n+1)/2 where n is the length, all substrings are included.
Maximum string length (consider memory and integer overflow)	Use long data type to store the sum of appeal if necessary to prevent integer overflow.
String with a wide variety of characters, including special characters and numbers	The algorithm should work correctly with any character set as long as it can be iterated over.
Very long string with many repeated characters	Ensure the algorithm's time complexity remains within acceptable limits, ideally O(n).
String containing Unicode characters	The algorithm should handle Unicode characters correctly by using appropriate string processing methods.

Empty String

How to Handle:

Return 0 as an empty string has no appeal.

Null String

How to Handle:

Throw IllegalArgumentException or return 0, depending on specification.

String with only one character

How to Handle:

Return 1 as the only substring is the character itself.

String with all identical characters (e.g., 'aaaa')

How to Handle:

The number of substrings is n*(n+1)/2 where n is the length, all substrings are included.

Maximum string length (consider memory and integer overflow)

How to Handle:

Use long data type to store the sum of appeal if necessary to prevent integer overflow.

String with a wide variety of characters, including special characters and numbers

How to Handle:

The algorithm should work correctly with any character set as long as it can be iterated over.

Very long string with many repeated characters

How to Handle:

Ensure the algorithm's time complexity remains within acceptable limits, ideally O(n).

String containing Unicode characters

How to Handle:

The algorithm should handle Unicode characters correctly by using appropriate string processing methods.