Problem

You are given a 0-indexed string s consisting of only lowercase English letters. Return _the number ofsubstrings in _s that begin and end with thesame character.

A substring is a contiguous non-empty sequence of characters within a string.

Examples

Example 1:

1
2
3
4
5
6

Input: s = "abcba"
Output: 7
Explanation:
The substrings of length 1 that start and end with the same letter are: "a", "b", "c", "b", and "a".
The substring of length 3 that starts and ends with the same letter is: "bcb".
The substring of length 5 that starts and ends with the same letter is: "abcba".

Example 2:

1
2
3
4
5
6

Input: s = "abacad"
Output: 9
Explanation:
The substrings of length 1 that start and end with the same letter are: "a", "b", "a", "c", "a", and "d".
The substrings of length 3 that start and end with the same letter are: "aba" and "aca".
The substring of length 5 that starts and ends with the same letter is: "abaca".

Example 3:

1
2
3
4

Input: s = "a"
Output: 1
Explanation:
The substring of length 1 that starts and ends with the same letter is: "a".

Constraints:

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters.

Solution

Method 1 – Counting by Character

Intuition

For each character, count how many times it appears. For each such character, the number of substrings that start and end with it is count * (count + 1) // 2 (all single letters plus all pairs, triples, etc.).

Approach

  1. Count the frequency of each character in the string.
  2. For each character, add count * (count + 1) // 2 to the answer.
  3. Return the total.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    long long numberOfSubstrings(string s) {
        vector<long long> cnt(26);
        for (char c : s) cnt[c - 'a']++;
        long long ans = 0;
        for (int i = 0; i < 26; ++i) ans += cnt[i] * (cnt[i] + 1) / 2;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func numberOfSubstrings(s string) int64 {
    cnt := make([]int64, 26)
    for _, c := range s {
        cnt[c-'a']++
    }
    var ans int64
    for i := 0; i < 26; i++ {
        ans += cnt[i] * (cnt[i] + 1) / 2
    }
    return ans
}
1
2
3
4
5
6
7
8
9

class Solution {
    public long numberOfSubstrings(String s) {
        long[] cnt = new long[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        long ans = 0;
        for (int i = 0; i < 26; i++) ans += cnt[i] * (cnt[i] + 1) / 2;
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun numberOfSubstrings(s: String): Long {
        val cnt = LongArray(26)
        for (c in s) cnt[c - 'a']++
        var ans = 0L
        for (i in 0..25) ans += cnt[i] * (cnt[i] + 1) / 2
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - ord('a')] += 1
        ans = 0
        for x in cnt:
            ans += x * (x + 1) // 2
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn number_of_substrings(s: String) -> i64 {
        let mut cnt = [0i64; 26];
        for c in s.chars() {
            cnt[(c as u8 - b'a') as usize] += 1;
        }
        let mut ans = 0i64;
        for x in cnt.iter() {
            ans += x * (x + 1) / 2;
        }
        ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    numberOfSubstrings(s: string): number {
        const cnt = new Array(26).fill(0);
        for (const c of s) cnt[c.charCodeAt(0) - 97]++;
        let ans = 0;
        for (const x of cnt) ans += x * (x + 1) / 2;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each character is processed once, and the final sum is over 26 letters.
  • 🧺 Space complexity: O(1) — Only a fixed-size array is used for counting.