2262. Total Appeal of A String
Description
The appeal of a string is the number of distinct characters found in the string.
- For example, the appeal of
"abbca"
is3
because it has3
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 <= 105
s
consists of lowercase English letters.
Solutions
Solution 1: Enumeration
We can enumerate all the substrings that end with each character $s[i]$ and calculate their gravitational value sum $t$. Finally, we add up all the $t$ to get the total gravitational value sum.
When we reach $s[i]$, which is added to the end of the substring that ends with $s[i-1]$, we consider the change of the gravitational value sum $t$:
If $s[i]$ has not appeared before, then the gravitational value of all substrings that end with $s[i-1]$ will increase by $1$, and there are a total of $i$ such substrings. Therefore, $t$ increases by $i$, plus the gravitational value of $s[i]$ itself, which is $1$. Therefore, $t$ increases by a total of $i+1$.
If $s[i]$ has appeared before, let the last appearance position be $j$. Then we add $s[i]$ to the end of the substrings $s[0..i-1]$, $[1..i-1]$, $s[2..i-1]$, $\cdots$, $s[j..i-1]$. The gravitational value of these substrings will not change because $s[i]$ has already appeared in these substrings. The gravitational value of the substrings $s[j+1..i-1]$, $s[j+2..i-1]$, $\cdots$, $s[i-1]$ will increase by $1$, and there are a total of $i-j-1$ such substrings. Therefore, $t$ increases by $i-j-1$, plus the gravitational value of $s[i]$ itself, which is $1$. Therefore, $t$ increases by a total of $i-j$. Therefore, we can use an array $pos$ to record the last appearance position of each character. Initially, all positions are set to $-1$.
Next, we traverse the string, and each time we update the gravitational value sum $t$ of the substring that ends with the current character to $t = t + i - pos[c]$, where $c$ is the current character. We add $t$ to the answer. Then we update $pos[c]$ to the current position $i$. We continue to traverse until the end of the string.
The time complexity is $O(n)$, and the space complexity is $O(|\Sigma|)$, where $n$ is the length of the string $s$, and $|\Sigma|$ is the size of the character set. In this problem, $|\Sigma| = 26$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|