2083. 求以相同字母开头和结尾的子串总数 🔒

题目描述

给你一个仅由小写英文字母组成的，下标从 0 开始的字符串 s 。返回 s 中以相同字符开头和结尾的子字符串总数。

子字符串是字符串中连续的非空字符序列。

示例 1：

输入：s = "abcba"
输出：7
解释：
以相同字母开头和结尾的长度为 1 的子串是："a"、"b"、"c"、"b" 和 "a" 。
以相同字母开头和结尾的长度为 3 的子串是："bcb" 。
以相同字母开头和结尾的长度为 5 的子串是："abcba" 。

示例 2：

输入：s = "abacad"
输出：9
解释：
以相同字母开头和结尾的长度为 1 的子串是："a"、"b"、"a"、"c"、"a" 和 "d" 。
以相同字母开头和结尾的长度为 3 的子串是："aba" 和 "aca" 。
以相同字母开头和结尾的长度为 5 的子串是："abaca" 。

示例 3：

输入：s = "a"
输出：1
解释：
只有一个，以相同字母开头和结尾的长度为 1 的子串是："a"。

提示：

1 <= s.length <= 10⁵
s 仅包含小写英文字母。

解法

方法一：数组或哈希表

我们可以用哈希表或者一个长度为 \(26\) 的数组 \(\textit{cnt}\) 来记录每个字符出现的次数。

遍历字符串 \(\textit{s}\)，对于每个字符 \(\textit{c}\)，我们将 \(\textit{cnt}[c]\) 的值加 \(1\)，然后将 \(\textit{cnt}[c]\) 的值加到答案中。

最后返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(\textit{s}\) 的长度。空间复杂度 \(O(|\Sigma|)\)，其中 \(\Sigma\) 是字符集，这里是小写英文字母，所以 \(|\Sigma|=26\)。

Python3JavaC++GoTypeScriptRustJavaScript

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        cnt = Counter()
        ans = 0
        for c in s:
            cnt[c] += 1
            ans += cnt[c]
        return ans

class Solution {
    public long numberOfSubstrings(String s) {
        int[] cnt = new int[26];
        long ans = 0;
        for (char c : s.toCharArray()) {
            ans += ++cnt[c - 'a'];
        }
        return ans;
    }
}

class Solution {
public:
    long long numberOfSubstrings(string s) {
        int cnt[26]{};
        long long ans = 0;
        for (char& c : s) {
            ans += ++cnt[c - 'a'];
        }
        return ans;
    }
};

func numberOfSubstrings(s string) (ans int64) {
    cnt := [26]int{}
    for _, c := range s {
        c -= 'a'
        cnt[c]++
        ans += int64(cnt[c])
    }
    return ans
}

function numberOfSubstrings(s: string): number {
    const cnt: Record<string, number> = {};
    let ans = 0;
    for (const c of s) {
        cnt[c] = (cnt[c] || 0) + 1;
        ans += cnt[c];
    }
    return ans;
}

impl Solution {
    pub fn number_of_substrings(s: String) -> i64 {
        let mut cnt = [0; 26];
        let mut ans = 0_i64;
        for c in s.chars() {
            let idx = (c as u8 - b'a') as usize;
            cnt[idx] += 1;
            ans += cnt[idx];
        }
        ans
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function (s) {
    const cnt = {};
    let ans = 0;
    for (const c of s) {
        cnt[c] = (cnt[c] || 0) + 1;
        ans += cnt[c];
    }
    return ans;
};

2083. 求以相同字母开头和结尾的子串总数 🔒

题目描述

解法

方法一：数组或哈希表

评论