2262. Total Appeal of A String

Problem Description

The goal is to calculate the total appeal of all possible substrings of a given string. The appeal of a string is determined by the number of distinct characters it contains. For instance, the string "abbca" contains three distinct characters, 'a', 'b', and 'c', therefore its appeal is 3.

To find the total appeal, we must consider each substring of the input string. A substring is defined as any contiguous sequence of characters within the string. For example, the string "abc" has the following substrings: "a", "b", "c", "ab", "bc", "abc". Each substring has its own appeal, and the total appeal is the sum of the appeals of all these substrings.

The challenge lies in efficiently computing this sum without having to explicitly check each substring, as there could be a large number of them.

Intuition

The presented solution takes a dynamic approach to calculate the total appeal. It optimizes the process by not generating each substring, but instead, keeping track of how each new character added to the end of the substrings affects their overall appeal.

The crux of the approach relies on two key observations:

When a new character is added that hasn't been seen before in any of the previous substrings, it increases the appeal of all the substrings ending at the previous character by one.
If the new character has been seen before, only the substrings that started after the last occurrence of this character have their appeal increased by one.

To keep track of these effects, an array pos is used to record the last position where each character occurred in the string (-1 if the character hasn't occurred yet).

As we iterate through the string character by character, we adjust the running total appeal t by considering the difference between the current index i and the last occurrence pos[c]. This efficiently calculates the incremental appeal contributed by the current character to all substrings ending with it.

By summing up these incremental contributions t as we go along, we obtain the total appeal of all substrings by the end of the traversal. This method avoids the overhead of explicit substring enumeration and appeal calculation, leading to a much faster solution.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological SortUniform Cost SearchMonotonic StackMemoization

I don’t know

Solution Approach

The solution implements an efficient algorithm to calculate the total appeal of all substrings of a given string. It uses a simple linear-time algorithm that leverages a concept similar to dynamic programming, along with an integer array to keep track of the last occurrence of characters.

The key steps in the algorithm include:

Initialize an array pos with length 26 (since there are 26 lowercase letters in the English alphabet) and fill it with -1. This array is used to store the last position where each character was seen in the string.
Initialize two integers: ans to accumulate the total appeal and t to keep track of the current sum of appeals as the algorithm iterates through the string.
Iterate over each character c in the string s, using an index i to keep track of the position.
Convert the character c into an array index (0-25) by subtracting the ASCII code of 'a' from the ASCII code of c.
Update t by adding the difference between i and the last occurrence of c (which is pos[c]). This captures the increase in appeal for all substrings ending at the current character, as explained in the intuition section.
Add the updated t to ans, incrementally building up the total appeal.
Finally, update the last occurrence of c in pos to the current index i.
Continue the iteration until the end of the string and return ans as the total appeal.

The code uses the fact that updating the total appeal with each new character and calculating the incremental appeal based on the last occurrence is sufficient to count the appeal for all possible substrings.

This approach results in O(n) time complexity, where n is the length of the input string. It avoids the need for nested loops, which would result in a higher time complexity. Additionally, the space complexity is O(1) since the auxiliary space used (the pos array) does not grow with the size of the input string.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the string "abaca".

Initialization: We start by initializing the array pos with size 26, to represent each letter in the English alphabet, and fill it with -1, indicating that none of the characters have been seen yet. We also initialize ans (accumulated total appeal) and t (current sum of appeals) to 0.

pos is initially [-1, -1, -1, ..., -1], ans = 0, and t = 0.
Iteration:
- Character 'a' at index 0: The index for 'a' is 0 - 'a' = 0. Since 'a' was not seen before (pos[0] == -1), t is updated by 0 - (-1) = 1. Then ans is updated by adding t to it (now ans = 1). The position of 'a' is updated in pos as pos[0] = 0.
- Character 'b' at index 1: Similar to 'a', 'b' has not been seen before. The index for 'b' is 1 - 'a' = 1. t is updated by 1 - (-1) = 2. Now ans += t (now ans = 3). Update pos[1] with the current index (pos[1] = 1).
- Character 'a' at index 2: 'a' has been seen before at index 0. The index for 'a' is 0. t is updated by 2 - 0 = 2. Add t to ans (now ans = 3 + 2 = 5). Update pos[0] with the current index (pos[0] = 2).
- Character 'c' at index 3: 'c' has not been seen before. The index for 'c' is 2 - 'a' = 2. t is updated by 3 - (-1) = 4. ans += t (now ans = 5 + 4 = 9). Update pos[2] with the current index (pos[2] = 3).
- Character 'a' at index 4: 'a' has been seen before at index 2. The index for 'a' is 0. t is updated by 4 - 2 = 2. ans += t (now ans = 9 + 2 = 11). Update pos[0] with the current index (pos[0] = 4).
Result: After iterating through the entire string, ans holds the total appeal of all possible substrings, which is 11 for the example string "abaca".

This walkthrough demonstrates how the solution efficiently calculates each character's contribution to the total appeal as we process the string, resulting in an optimal calculation without examining each substring individually.

Solution Implementation

1class Solution:
2    def appealSum(self, s: str) -> int:
3        total_appeal = current_sum = 0  # Initialize total appeal and current sum of appeal
4        last_positions = [-1] * 26  # Initialize list to store the last positions of characters
5      
6        # Loop through the string with index and character
7        for index, char in enumerate(s):
8            char_code = ord(char) - ord('a')  # Convert character to a number (0-25)
9          
10            # Update current sum by adding the difference between current index and last seen position
11            current_sum += index - last_positions[char_code]
12          
13            # Add the updated current sum to the total appeal
14            total_appeal += current_sum
15          
16            # Update the last seen position of this character
17            last_positions[char_code] = index
18      
19        return total_appeal  # Return the total appeal of the substring
20

1class Solution {
2    // This method calculates the sum of the appeal of all substrings of a given string s.
3    // The appeal of a string is defined as the number of distinct characters found in the string.
4    public long appealSum(String s) {
5        long totalAppeal = 0;   // This variable will store the sum of the appeal of all substrings.
6        long currentAppeal = 0; // This variable stores the appeal of the substring ending at the current character.
7        int[] lastPosition = new int[26]; // An array to store the last position of each character.
8        Arrays.fill(lastPosition, -1); // Initialize last positions to -1 for all characters.
9      
10        // Iterate over each character in the string to compute the appeal of all possible substrings.
11        for (int i = 0; i < s.length(); ++i) {
12            int charIndex = s.charAt(i) - 'a'; // Convert the char to an index 0-25 corresponding to 'a'-'z'.
13            // Update the current appeal by adding the contribution of the current character.
14            // The contribution is the difference between the current position and its last seen position.
15            currentAppeal += i - lastPosition[charIndex];
16            // Add the current appeal to the total appeal.
17            totalAppeal += currentAppeal;
18            // Update the last seen position for the current character.
19            lastPosition[charIndex] = i;
20        }
21      
22        // Return the total appeal sum of all substrings.
23        return totalAppeal;
24    }
25}
26

1class Solution {
2public:
3    long long appealSum(string s) {
4        long long totalAppeal = 0; // This will hold the sum of appeals of all substrings.
5        long long currentAppeal = 0; // This will keep track of the appeal of the current substring.
6        vector<int> lastPosition(26, -1); // Keeps track of the last position of each character in the alphabet within the string.
7
8        // Loop through each character in the string.
9        for (int i = 0; i < s.size(); ++i) {
10            int charIndex = s[i] - 'a'; // Convert the current character to an index (0-25) corresponding to a-z.
11
12            // The appeal of a substring extends by the distance from the last occurrence of the current character.
13            currentAppeal += i - lastPosition[charIndex];
14
15            // Add the current substring's appeal to the total.
16            totalAppeal += currentAppeal;
17
18            // Update the last seen position for the current character.
19            lastPosition[charIndex] = i;
20        }
21
22        // Return the total appeal which is the sum of appeals of all substrings.
23        return totalAppeal;
24    }
25};
26

1function appealSum(s: string): number {
2    // Initialize an array to keep track of the last seen position of each character
3    // and fill it with -1, indicating that none have been seen yet.
4    const lastPosition: number[] = Array(26).fill(-1); // 26 letters in the alphabet
5    const stringLength = s.length;
6    let totalAppeal = 0; // This will accumulate the total appeal of all substrings
7    let currentAppeal = 0; // This keeps the running sum of appeals
8
9    // Iterate through each character in the string
10    for (let index = 0; index < stringLength; ++index) {
11        // Convert the current character to its alphabet position (0 for 'a', 1 for 'b', etc.)
12        const charCode = s.charCodeAt(index) - 'a'.charCodeAt(0);
13        // Update the running sum of appeals by adding the distance from the last seen position
14        currentAppeal += index - lastPosition[charCode];
15        // Add the current appeal to total appeal
16        totalAppeal += currentAppeal;
17        // Update the last seen position of the current character
18        lastPosition[charCode] = index;
19    }
20
21    // Return the calculated total appeal
22    return totalAppeal;
23}
24

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Time and Space Complexity

The given code calculates the sum of the appeals of all substrings of a string.

Time Complexity

We iterate through each character in the input string only once. The loop runs for n iterations if n is the length of the input string s.

Inside the loop, we perform constant-time operations: indexing an array (pos[c]), arithmetic operations (t += i - pos[c] and ans += t), and updating an array element (pos[c] = i). Since these operations do not depend on the size of n and are done in constant time, the time complexity of the loop is O(n).

Therefore, the overall time complexity of the code is O(n).

Space Complexity

We are using an extra array pos of size 26 to keep track of the last positions of each character that appears in the string. The size of this array depends on the size of the character set |\Sigma|, which in this case is the English alphabet and hence |\Sigma| = 26.

Therefore, the space complexity of the code is O(|\Sigma|), which is O(26) for this problem.

Since 26 is a constant and does not change with the input size, we could also consider the space complexity as O(1), constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2262. Total Appeal of A String

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings