Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2262.html
2262. Total Appeal of A String
 Difficulty: Hard.
 Related Topics: Hash Table, String, Dynamic Programming.
 Similar Questions: Count Unique Characters of All Substrings of a Given String, Count Vowel Substrings of a String, Vowels of All Substrings.
Problem
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.
Solution

class Solution { public long appealSum(String s) { int len = s.length(); int[] lastPos = new int[26]; Arrays.fill(lastPos, 1); long res = 0; for (int i = 0; i < len; i++) { int idx = s.charAt(i)  'a'; res += (i  lastPos[idx]) * (len  i); lastPos[idx] = i; } return res; } } ############ 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; } }

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 ############ # 2262. Total Appeal of A String # https://leetcode.com/problems/totalappealofastring/ class Solution: def appealSum(self, s: str) > int: n = len(s) def go(k): count = total = 0 for x in s: if x == k: total += (count * (count + 1)) // 2 count = 0 else: count += 1 total += (count * (count + 1)) // 2 return (n * (n + 1)) // 2  total res = 0 for k in string.ascii_lowercase: res += go(k) return res

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; } };

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 }

function appealSum(s: string): number { const n = s.length; let dp = new Array(n + 1).fill(0); const hashMap = new Map(); for (let i = 0; i < n; i++) { const c = s.charAt(i); dp[i + 1] = dp[i] + i + 1  (hashMap.get(c)  0); hashMap.set(c, i + 1); } return dp.reduce((a, c) => a + c, 0); }
Explain:
nope.
Complexity:
 Time complexity : O(n).
 Space complexity : O(n).