README.md

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

English Version

题目描述

给你一个仅由小写英文字母组成的，  下标从 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 <= 105
• s 仅包含小写英文字母。

解法

前缀和 + 计数器。

用 counter 累计以每个字符结尾的字符串的个数。

遍历字符串 s 中每个字符 c，累加以 c 字符串结尾的字符串个数。

Python3

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        counter = [0] * 26
        ans = 0
        for c in s:
            i = ord(c) - ord('a')
            counter[i] += 1
            ans += counter[i]
        return ans

Java

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

C++

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

Go

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

...