Algorithm
Problem Name: 828. Count Unique Characters of All Substrings of a Given String
Problem Link: https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/
Let's define a function countUniqueChars(s) that returns the number of unique characters on s.
- For example, calling
countUniqueChars(s)ifs = "LEETCODE"then"L","T","C","O","D"are the unique characters since they appear only once ins, thereforecountUniqueChars(s) = 5.
Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.
Notice that some substrings can be repeated so in this case you have to count the repeated ones too.
Example 1:
Input: s = "ABC" Output: 10 Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC". Every substring is composed with only unique letters. Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
Example 2:
Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.
Example 3:
Input: s = "LEETCODE" Output: 92
Constraints:
1 <= s.length <= 105sconsists of uppercase English letters only.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const uniqueLetterString = function(s) {
const n = s.length
const arr = Array.from({ length: 26 }, () => Array(2).fill(-1))
const A = 'A'.charCodeAt(0)
let res = 0
for(let i = 0; i < n; i++) {
const idx = s.charCodeAt(i) - A
res += (i - arr[idx][1]) * (arr[idx][1] - arr[idx][0])
arr[idx] = [arr[idx][1], i]
}
for(let i = 0; i < 26; i++) {
res += (n - arr[i][1]) * (arr[i][1] - arr[i][0])
}
return res
};
Input
Output
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def uniqueLetterString(self, S):
index = {c: [-1, -1] for c in string.ascii_uppercase}
res = 0
for i, c in enumerate(S):
k, j = index[c]
res += (i - j) * (j - k)
index[c] = [j, i]
for c in index:
k, j = index[c]
res += (len(S) - j) * (j - k)
return res % (10**9 + 7)
Input
Output