LeetCode 2083. Substrings That Begin and End With the Same Letter Solution in Java, C++, Python & More | Explanation + Code

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

Solutions

Solution 1: Array or Hash Table

We can use a hash table or an array cnt of length 26 to record the occurrences of each character.

Traverse the string s. For each character c, increment the value of cnt[c] by 1, and then add the value of cnt[c] to the answer.

Finally, return the answer.

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

PythonJavaC++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(code-box)

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; } }(code-box)

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; } };(code-box)

func numberOfSubstrings(s string) (ans int64) { cnt := [26]int{} for _, c := range s { c -= 'a' cnt[c]++ ans += int64(cnt[c]) } return ans }(code-box)

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; }(code-box)

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 } }(code-box)

/** * @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; };(code-box)