思路：遍历枚举

考虑枚举字符串的尾字符，那么对于首字符，就是尾字符前面与其相等的字符，都可以作为字符串的首字符。特别地，长度为 11 的字符串也是符合题意的。

所以只需要统计 26 个字符的数目，开一个长度为 26 的数组统计数量即可。

时间复杂度：$O(n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    vector<int> cnt(26, 0);

    long long ans = 0;
    for (auto c: s) {
        cnt[c - 'a'] += 1;
        ans += cnt[c - 'a'];
    }

    cout << ans << "\n";

    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();

        int[] cnt = new int[26];
        long ans = 0;

        for (char c : s.toCharArray()) {
            cnt[c - 'a'] += 1;
            ans += cnt[c - 'a'];
        }

        System.out.println(ans);
    }
}

Python

s = input()

cnt = [0] * 26
ans = 0

for c in s:
    cnt[ord(c) - ord('a')] += 1
    ans += cnt[ord(c) - ord('a')]

print(ans)

题目描述

小红有一个字符串 $s$ 。

现在，他想让你求一下这个串中首尾字符相同的子串数目。

输入描述

一行，一个只包括小写字母的字符串 $s(1\leq |s|\leq 10^5)$ 。

输出描述

一个整数，字符串中首尾字符相同的子串数目。

样例

输入

aaa

输出

6

说明

长度为 $1$ 的三个子串 "a" 长度为 $2$ 的两个子串 "aa" 长度为 $3$ 的一个子串 "aaa"