class Solution {
public:
int uniqueLetterString(string s) {
}
};
828. 统计子串中的唯一字符
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。
注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
示例 1：
输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
示例 2：
输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
示例 3：
输入：s = "LEETCODE" 输出：92
提示：
1 <= s.length <= 10^5s 只包含大写英文字符原站题解
rust 解法, 执行用时: 8 ms, 内存消耗: 2.6 MB, 提交时间: 2023-11-26 14:49:27
impl Solution {
pub fn unique_letter_string(s: String) -> i32 {
let mut d: Vec<Vec<i32>> = vec![vec![-1; 1]; 26];
for (i, c) in s.chars().enumerate() {
d[(c as usize) - ('A' as usize)].push(i as i32);
}
let mut ans = 0;
for v in d.iter_mut() {
v.push(s.len() as i32);
for i in 1..v.len() - 1 {
ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i]);
}
}
ans as i32
}
}
java 解法, 执行用时: 7 ms, 内存消耗: 43.2 MB, 提交时间: 2023-05-24 17:44:14
class Solution {
public int uniqueLetterString(String s) {
int ans = 0, total = 0;
int[] last0 = new int[26], last1 = new int[26];
Arrays.fill(last0, -1);
Arrays.fill(last1, -1);
for (var i = 0; i < s.length(); i++) {
var c = s.charAt(i) - 'A';
total += i - 2 * last0[c] + last1[c];
ans += total;
last1[c] = last0[c];
last0[c] = i;
}
return ans;
}
}
python3 解法, 执行用时: 268 ms, 内存消耗: 16.7 MB, 提交时间: 2023-05-24 17:43:59
class Solution:
def uniqueLetterString(self, s: str) -> int:
ans = total = 0
last0, last1 = {}, {}
for i, c in enumerate(s):
total += i - 2 * last0.get(c, -1) + last1.get(c, -1)
ans += total
last1[c] = last0.get(c, -1)
last0[c] = i
return ans
golang 解法, 执行用时: 8 ms, 内存消耗: 6.1 MB, 提交时间: 2023-05-24 17:43:40
func uniqueLetterString(s string) (ans int) {
last0, last1, total := [26]int{}, [26]int{}, 0
for i := range last0 {
last0[i] = -1
last1[i] = -1
}
for i, c := range s {
c -= 'A'
total += i - 2*last0[c] + last1[c]
ans += total
last1[c] = last0[c]
last0[c] = i
}
return
}
golang 解法, 执行用时: 44 ms, 内存消耗: 7 MB, 提交时间: 2023-05-24 17:43:10
func uniqueLetterString(s string) (ans int) {
dict := map[rune][]int{}
for i, c := range s {
if v, ok := dict[c]; ok {
dict[c] = append(v, i)
} else {
dict[c] = []int{-1, i}
}
}
for _, v := range dict {
v = append(v, len(s))
for i := 1; i < len(v) - 1; i++ {
ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i])
}
}
return
}
java 解法, 执行用时: 61 ms, 内存消耗: 53.2 MB, 提交时间: 2023-05-24 17:42:46
class Solution {
public int uniqueLetterString(String s) {
Map<Character, List<Integer>> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
List<Integer> list = map.getOrDefault(c, new ArrayList<>(){{add(-1);}});
list.add(i);
map.put(c, list);
}
int ans = 0;
for (List<Integer> list: map.values()) {
list.add(s.length());
for (int i = 1; i < list.size() - 1; i++) {
ans += (list.get(i) - list.get(i - 1)) * (list.get(i + 1) - list.get(i));
}
}
return ans;
}
}
python3 解法, 执行用时: 244 ms, 内存消耗: 20.8 MB, 提交时间: 2023-05-24 17:42:33
'''
设字符c位于[left, right]中的idx且c唯一,
那么c出现的次数为它左边包含它的个数乘它右边包含它的个数
[即(idx + 1 - left) * (right + 1 - left)]。
所以我们只需要统计每个字符出现的所有间隔坐标即可。
'''
class Solution:
def uniqueLetterString(self, s: str) -> int:
d = defaultdict(list)
for i, c in enumerate(s):
d[c].append(i)
ans = 0
for v in d.values():
cur = [-1] + v + [len(s)]
for i in range(1, len(cur) - 1):
ans += (cur[i] - cur[i - 1]) * (cur[i + 1] - cur[i])
return ans
cpp 解法, 执行用时: 36 ms, 内存消耗: 24.4 MB, 提交时间: 2023-05-24 17:40:46
/**
题目求：s的所有子串中唯一字符的数量有多少
等价于：s中的每个字符是唯一字符的子串有多少
等价问题比原问题更好求解！
我们只要记录每个字符在s中出现的位置
假设s[b]前一次出现的位置是s[a],后一次出现的位置是s[c]
那么以s[b]为唯一字符的最长子串为s(a, c)
现在我们要求以s[b]为唯一字符的子串数量
子串要包含s[b],因此把这个最长子串以s[b]划分为左右两段
左边可取的长度为b-a,右边可取的长度为c-b
因此，以s[b]为唯一字符的子串数量为(b-a)*(c-b)
*/
class Solution {
public:
int uniqueLetterString(string s) {
int n = s.size();
// 字符位置
vector<int> pos[26];
// 左边界
for (int i = 0; i < 26; i++) pos[i].push_back(-1);
// 记录字符位置
for (int i = 0; i < n; i++) pos[s[i] - 'A'].push_back(i);
// 右边界
for (int i = 0; i < 26; i++) pos[i].push_back(n);
int res = 0;
// 遍历字母
for (int i = 0; i < 26; i++) {
// 遍历位置
// ?????A????A?????A????
// ....j-1...j....j+1...
for (int j = 1; j + 1 < pos[i].size(); j++) {
// s[pos[i][j-1]] ~ s[pos[i][j+1]]是s[pos[i][j]]为唯一字符的子串
res += (pos[i][j] - pos[i][j-1]) * (pos[i][j+1] - pos[i][j]);
}
}
return res;
}
};