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 <= 105s consists only of lowercase English letters.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(|\Sigma|), where \Sigma is the character set. Here, it is lowercase English letters, so |\Sigma|=26.
Java
C++
Go
TypeScript
Rust
JavaScript
Palindromic Substrings - Leetcode 647 - Python • NeetCode • 177,962 views views
Watch 9 more video solutions →Practice Substrings That Begin and End With the Same Letter with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor