2083. Substrings That Begin and End With the Same Letter 🔒

Description

You are given a 0-indexed string s consisting of only lowercase English letters. Return the number of substrings in s that begin and end with the same character.

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

Example 1:

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:

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:

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⁵
s consists only of lowercase English letters.

Solutions

Solution 1: Array or Hash Table

We can use a hash table or an array \(\textit{cnt}\) of length \(26\) to record the occurrences of each character.

Traverse the string \(\textit{s}\). For each character \(\textit{c}\), increment the value of \(\textit{cnt}[c]\) by \(1\), and then add the value of \(\textit{cnt}[c]\) to the answer.

Finally, return the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(\textit{s}\). The space complexity is \(O(|\Sigma|)\), where \(\Sigma\) is the character set. Here, it is lowercase English letters, so \(|\Sigma|=26\).

Python3JavaC++GoTypeScriptRustJavaScript

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 (char c : s.toCharArray()) {
            ans += ++cnt[c - 'a'];
        }
        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
}

function numberOfSubstrings(s: string): number {
    const cnt: Record<string, number> = {};
    let ans = 0;
    for (const c of s) {
        cnt[c] = (cnt[c] || 0) + 1;
        ans += cnt[c];
    }
    return ans;
}

impl Solution {
    pub fn number_of_substrings(s: String) -> i64 {
        let mut cnt = [0; 26];
        let mut ans = 0_i64;
        for c in s.chars() {
            let idx = (c as u8 - b'a') as usize;
            cnt[idx] += 1;
            ans += cnt[idx];
        }
        ans
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function (s) {
    const cnt = {};
    let ans = 0;
    for (const c of s) {
        cnt[c] = (cnt[c] || 0) + 1;
        ans += cnt[c];
    }
    return ans;
};

2083. Substrings That Begin and End With the Same Letter 🔒

Description

Solutions

Solution 1: Array or Hash Table

Comments