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" 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.

Solution

• Java
• Python
• C++
• Go
• TypeScript

• 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/total-appeal-of-a-string/
  
  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).

All Problems

All Solutions