Skip to content

Files

Latest commit

 

History

History
 
 

2083.Substrings That Begin and End With the Same Letter

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 

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
}

...