Question

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 仅包含小写英文字母。

解法

方法一：数组或哈希表

我们可以用数组或哈希表统计字符串中每个字母出现的次数，然后遍历字符串，对于每个字母，其出现的次数即为以该字母开头和结尾的子串的个数，将所有字母的出现次数相加即为答案。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串的长度，而 $C$ 为字符集的大小。本题中 $C = 26$。

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 (int i = 0; i < s.length(); ++i) {
      int j = s.charAt(i) - 'a';
      ++cnt[j];
      ans += cnt[j];
    }
    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
}