LeetCode 2262. Total Appeal of A String Solution in Java, C++, Python & More | Explanation + Code

Description

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 <= 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], …, 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], …, 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(|Σ|), where n is the length of the string s, and |Σ| is the size of the character set. In this problem, |Σ| = 26.

PythonJavaC++GoTypeScript

class Solution: def appealSum(self, s: str) -> int: ans = t = 0 pos = [-1] * 26 for i, c in enumerate(s): c = ord(c) - ord('a') t += i - pos[c] ans += t pos[c] = i return ans(code-box)

class Solution { public long appealSum(String s) { long ans = 0; long t = 0; int[] pos = new int[26]; Arrays.fill(pos, -1); for (int i = 0; i < s.length(); ++i) { int c = s.charAt(i) - 'a'; t += i - pos[c]; ans += t; pos[c] = i; } return ans; } }(code-box)

class Solution { public: long long appealSum(string s) { long long ans = 0, t = 0; vector<int> pos(26, -1); for (int i = 0; i < s.size(); ++i) { int c = s[i] - 'a'; t += i - pos[c]; ans += t; pos[c] = i; } return ans; } };(code-box)

func appealSum(s string) int64 { var ans, t int64 pos := make([]int, 26) for i := range pos { pos[i] = -1 } for i, c := range s { c -= 'a' t += int64(i - pos[c]) ans += t pos[c] = i } return ans }(code-box)

function appealSum(s: string): number { const pos: number[] = Array(26).fill(-1); const n = s.length; let ans = 0; let t = 0; for (let i = 0; i < n; ++i) { const c = s.charCodeAt(i) - 97; t += i - pos[c]; ans += t; pos[c] = i; } return ans; }(code-box)