2023-05-08：我們定義了一個(gè)函數(shù) countUniqueChars(s) 來(lái)統(tǒng)計(jì)字符串 s 中的唯一字符，

并返回唯一字符的個(gè)數(shù)。

例如：s = "LEETCODE" ，則其中 "L", "T","C","O","D" 都是唯一字符，

因?yàn)樗鼈冎怀霈F(xiàn)一次，所以 countUniqueChars(s) = 5 。

本題將會(huì)給你一個(gè)字符串 s ，我們需要返回 countUniqueChars(t) 的總和，

其中 t 是 s 的子字符串。輸入用例保證返回值為 32 位整數(shù)。

注意，某些子字符串可能是重復(fù)的，但你統(tǒng)計(jì)時(shí)也必須算上這些重復(fù)的子字符串

（也就是說(shuō)，你必須統(tǒng)計(jì) s 的所有子字符串中的唯一字符）。

輸入: s = "ABC"。

輸出: 10。

答案2023-05-08：

1.定義函數(shù) countUniqueChars(s)，參數(shù)為字符串 s，返回值為整數(shù)。

2.創(chuàng)建一個(gè)空的哈希表 indies 來(lái)記錄每個(gè)字符出現(xiàn)的位置。

3.遍歷字符串 s 中的每個(gè)字符，對(duì)于每個(gè)字符：

3.1.檢查該字符是否已經(jīng)在 indies 中出現(xiàn)過(guò)，如果沒(méi)有則將其加入哈希表，并將初始位置 -1 添加到其位置數(shù)組中。

3.2.將當(dāng)前字符的位置添加到其位置數(shù)組中。

4.初始化計(jì)數(shù)器 res 為 0。

5.遍歷哈希表 indies 中的每個(gè)鍵值對(duì)，對(duì)于每個(gè)鍵值對(duì)：

5.1.在該鍵所對(duì)應(yīng)的位置數(shù)組的末尾添加字符串 s 的長(zhǎng)度，方便后續(xù)計(jì)算。

5.2.遍歷該鍵所對(duì)應(yīng)的位置數(shù)組中除了開(kāi)頭和結(jié)尾的位置，對(duì)于每組相鄰的位置 i 和 j，計(jì)算左側(cè)有多少個(gè)連續(xù)的該鍵字符和右側(cè)有多少個(gè)連續(xù)的該鍵字符，累加乘積到 res 中。

6.返回計(jì)數(shù)器 res。

注意：該題目要求統(tǒng)計(jì)所有子字符串中的唯一字符的數(shù)量，因此需要遍歷所有子串。具體實(shí)現(xiàn)方法可以枚舉所有子串，或者使用一個(gè)雙重循環(huán)來(lái)分別枚舉子串的起始位置和結(jié)束位置，時(shí)間復(fù)雜度為 O(n^3)，其中 n 是字符串 s 的長(zhǎng)度。但由于該題目的數(shù)據(jù)范圍較小，因此可以使用暴力枚舉來(lái)實(shí)現(xiàn)。

時(shí)間復(fù)雜度：

遍歷字符串 s 的時(shí)間復(fù)雜度為 O(n)，其中 n 是字符串的長(zhǎng)度。

遍歷哈希表 indies 中的每個(gè)位置數(shù)組的時(shí)間復(fù)雜度為 O(k)，其中 k 是該鍵對(duì)應(yīng)的字符在字符串 s 中出現(xiàn)的次數(shù)。

因此，整個(gè)程序的時(shí)間復(fù)雜度為 O(nk)。

額外空間復(fù)雜度：

哈希表 indies 和每個(gè)鍵所對(duì)應(yīng)的位置數(shù)組的空間復(fù)雜度都是 O(k)，其中 k 是該鍵對(duì)應(yīng)的字符在字符串 s 中出現(xiàn)的次數(shù)。因此，整個(gè)程序的額外空間復(fù)雜度為 O(nk)。

go完整代碼如下：

package main

import "fmt"

func uniqueLetterString(s string) int {
    // key : 某一種字符
    // value : 出現(xiàn)這種字符依次的位置
    indies := make(map[byte][]int)
    for i := 0; i < len(s); i++ {
        c := s[i]
        if _, ok := indies[c]; !ok {
            indies[c] = []int{-1}
        }
        indies[c] = append(indies[c], i)
    }
    res := 0
    for _, arr := range indies {
        arr = append(arr, len(s))
        for i := 1; i < len(arr)-1; i++ {
            res += (arr[i] - arr[i-1]) * (arr[i+1] - arr[i])
        }
    }
    return res
}

func main() {
    s := "ABC"
    res := uniqueLetterString(s)
    fmt.Println(res)
}

[圖片上傳失敗...(image-584ba7-1683552919656)]

rust完整代碼如下：

use std::collections::HashMap;

fn unique_letter_string(s: &str) -> i32 {
    // key : 某一種字符
    // value : 出現(xiàn)這種字符依次的位置
    let mut indies: HashMap<char, Vec<i32>> = HashMap::new();
    for (i, c) in s.chars().enumerate() {
        indies.entry(c).or_insert_with(Vec::new).push(i as i32);
    }
    let mut res = 0;
    for (_, arr) in indies.iter() {
        let mut arr = arr.clone();
        arr.insert(0, -1);
        arr.push(s.len() as i32);
        for i in 1..arr.len() - 1 {
            res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
        }
    }
    res as i32
}

fn main() {
    let s = "ABC";
    let res = unique_letter_string(s);
    println!("{}", res);
}

[圖片上傳失敗...(image-9a171a-1683552919656)]

c完整代碼如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000

struct Vector {
    int data[MAX_N];
    int size;
};

void vector_init(struct Vector* vec) {
    memset(vec->data, -1, sizeof(vec->data));
    vec->data[0] = -1;
    vec->size = 1;
}

void vector_push_back(struct Vector* vec, int x) {
    vec->data[vec->size++] = x;
}

int uniqueLetterString(char* s) {
    // key : 某一種字符
    // value : 出現(xiàn)這種字符依次的位置
    struct Vector indies[256];
    int cnt[256] = { 0 };
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (cnt[c] == 0) {
            vector_init(&indies[c]);
        }
        vector_push_back(&indies[c], i);
        cnt[c]++;
    }
    int res = 0;
    for (int c = 0; c < 256; c++) {
        if (cnt[c] == 0) continue;
        vector_push_back(&indies[c], strlen(s));
        for (int i = 1; i < indies[c].size - 1; i++) {
            int left = indies[c].data[i] - indies[c].data[i - 1];
            int right = indies[c].data[i + 1] - indies[c].data[i];
            res += left * right;
        }
    }
    return res;
}

int main() {
    char s[] = "ABC";
    int res = uniqueLetterString(s);
    printf("%d\n", res);
    return 0;
}

[圖片上傳失敗...(image-5afa6d-1683552919656)]

c++完整代碼如下：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int uniqueLetterString(string s) {
    // key : 某一種字符
    // value : 出現(xiàn)這種字符依次的位置
    unordered_map<char, vector<int>> indies;
    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        if (!indies.count(c)) {
            indies[c] = { -1 };
        }
        indies[c].push_back(i);
    }
    int res = 0;
    for (auto entry : indies) {
        auto arr = entry.second;
        arr.push_back(s.length());
        for (int i = 1; i < arr.size() - 1; i++) {
            res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
        }
    }
    return res;
}

int main() {
    string s = "ABC";
    int res = uniqueLetterString(s);
    cout << res << endl;
    return 0;
}

[圖片上傳失敗...(image-8e388c-1683552919656)]