Welcome to Subscribe On Youtube

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• RenderScript

• class Solution {
      public long numberOfSubstrings(String s) {
          int[] cnt = new int[26];
          long ans = 0;
          for (int i = 0; i < s.length(); ++i) {
              int j = s.charAt(i) - 'a';
              ++cnt[j];
              ans += cnt[j];
          }
          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;
      }
  };
  

• class Solution:
      def numberOfSubstrings(self, s: str) -> int:
          cnt = Counter()
          ans = 0
          for c in s:
              cnt[c] += 1
              ans += cnt[c]
          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;
  }
  
  

• /**
   * @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;
  };
  
  

• 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
      }
  }
  
  

All Problems

All Solutions