Let’s define a function countUniqueChars(s) that returns the number of unique characters in s.
For example, calling countUniqueChars(s) if s = "LEETCODE" then "L", "T", "C", "O", "D" are the unique characters since they appear only once in s, therefore countUniqueChars(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.
Input: s ="ABC"Output: 10Explanation: 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 is1+1+1+2+2+3=10
Each character’s contribution to the answer is determined by how many substrings it is unique in. For each occurrence of a character, we can find the distance to its previous and next occurrence, and the product of these distances gives the number of substrings where this character is unique.
For each character, store the indices of its occurrences in the string (add -1 at the start and n at the end for boundaries).
For each occurrence at index i, the number of substrings where it is unique is (i - prev) * (next - i), where prev and next are the previous and next occurrence indices.
classSolution {
public:int uniqueLetterString(string s) {
int n = s.size(), ans =0;
vector<vector<int>> pos(26, vector<int>{-1});
for (int i =0; i < n; ++i) pos[s[i] -'A'].push_back(i);
for (int c =0; c <26; ++c) pos[c].push_back(n);
for (int c =0; c <26; ++c) {
for (int i =1; i < pos[c].size() -1; ++i) {
ans += (pos[c][i] - pos[c][i-1]) * (pos[c][i+1] - pos[c][i]);
}
}
return ans;
}
};
classSolution {
publicintuniqueLetterString(String s) {
int n = s.length(), ans = 0;
List<Integer>[] pos =new List[26];
for (int i = 0; i < 26; i++) pos[i]=new ArrayList<>();
for (int i = 0; i < 26; i++) pos[i].add(-1);
for (int i = 0; i < n; i++) pos[s.charAt(i) -'A'].add(i);
for (int i = 0; i < 26; i++) pos[i].add(n);
for (int c = 0; c < 26; c++) {
for (int i = 1; i < pos[c].size() - 1; i++) {
ans += (pos[c].get(i) - pos[c].get(i-1)) * (pos[c].get(i+1) - pos[c].get(i));
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
fununiqueLetterString(s: String): Int {
val n = s.length
val pos = Array(26) { mutableListOf(-1) }
for (i in s.indices) pos[s[i] - 'A'].add(i)
for (p in pos) p.add(n)
var ans = 0for (p in pos) {
for (i in1 until p.size-1) {
ans += (p[i] - p[i-1]) * (p[i+1] - p[i])
}
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution:
defuniqueLetterString(self, s: str) -> int:
n = len(s)
pos = {c: [-1] for c in set(s)}
for i, ch in enumerate(s):
pos.setdefault(ch, [-1]).append(i)
for ch in pos:
pos[ch].append(n)
ans =0for ch in pos:
p = pos[ch]
for i in range(1, len(p)-1):
ans += (p[i] - p[i-1]) * (p[i+1] - p[i])
return ans
impl Solution {
pubfnunique_letter_string(s: String) -> i32 {
let n = s.len();
let s = s.as_bytes();
letmut pos =vec![vec![-1i32]; 26];
for (i, &c) in s.iter().enumerate() {
pos[(c -b'A') asusize].push(i asi32);
}
for p in pos.iter_mut() {
p.push(n asi32);
}
letmut ans =0;
for p in pos.iter() {
for i in1..p.len()-1 {
ans += (p[i] - p[i-1]) * (p[i+1] - p[i]);
}
}
ans
}
}