Welcome to Subscribe On Youtube

1180. Count Substrings with Only One Distinct Letter

Description

Given a string s, return the number of substrings that have only one distinct letter.

 

Example 1:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

Example 2:

Input: s = "aaaaaaaaaa"
Output: 55

 

Constraints:

• 1 <= s.length <= 1000
• s[i] consists of only lowercase English letters.

Solutions

Solution 1: Two Pointers

We can use two pointers, where pointer $i$ points to the start of the current substring, and pointer $j$ moves to the right to the first position that is different from $s[i]$. Then, $[i,..j-1]$ is a substring with $s[i]$ as the only character, and its length is $j-i$. Therefore, the number of substrings with $s[i]$ as the only character is $\frac{(j-i+1)(j-i)}{2}$, which is added to the answer. Then, we set $i=j$ and continue to traverse until $i$ exceeds the range of string $s$.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.

Solution 2

This implementation follows the required operations directly. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript
• Java 2
• C++ 2
• Python 2
• Go 2

• class Solution {
      public int countLetters(String s) {
          int ans = 0;
          for (int i = 0, n = s.length(); i < n;) {
              int j = i;
              while (j < n && s.charAt(j) == s.charAt(i)) {
                  ++j;
              }
              ans += (1 + j - i) * (j - i) / 2;
              i = j;
          }
          return ans;
      }
  }
  
  
  // Solution 2
  class Solution {
      public int countLetters(String s) {
          int ans = 0;
          int i = 0, n = s.length();
          while (i < n) {
              int j = i;
              int cnt = 0;
              while (j < n && s.charAt(j) == s.charAt(i)) {
                  ++j;
                  ans += ++cnt;
              }
              i = j;
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      int countLetters(string s) {
          int ans = 0;
          for (int i = 0, n = s.size(); i < n;) {
              int j = i;
              while (j < n && s[j] == s[i]) {
                  ++j;
              }
              ans += (1 + j - i) * (j - i) / 2;
              i = j;
          }
          return ans;
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      int countLetters(string s) {
          int ans = 0;
          int i = 0, n = s.size();
          while (i < n) {
              int j = i;
              int cnt = 0;
              while (j < n && s[j] == s[i]) {
                  ++j;
                  ans += ++cnt;
              }
              i = j;
          }
          return ans;
      }
  };
  
  

• class Solution:
      def countLetters(self, s: str) -> int:
          n = len(s)
          i = ans = 0
          while i < n:
              j = i
              while j < n and s[j] == s[i]:
                  j += 1
              ans += (1 + j - i) * (j - i) // 2
              i = j
          return ans
  
  
  # Solution 2
  class Solution:
      def countLetters(self, s: str) -> int:
          ans = 0
          i, n = 0, len(s)
          while i < n:
              j = i
              cnt = 0
              while j < n and s[j] == s[i]:
                  j += 1
                  cnt += 1
                  ans += cnt
              i = j
          return ans
  
  

• func countLetters(s string) int {
  	ans := 0
  	for i, n := 0, len(s); i < n; {
  		j := i
  		for j < n && s[j] == s[i] {
  			j++
  		}
  		ans += (1 + j - i) * (j - i) / 2
  		i = j
  	}
  	return ans
  }
  
  
  // Solution 2
  func countLetters(s string) (ans int) {
  	i, n := 0, len(s)
  	for i < n {
  		j := i
  		cnt := 0
  		for j < n && s[j] == s[i] {
  			j++
  			cnt++
  			ans += cnt
  		}
  		i = j
  	}
  	return
  }
  
  

• function countLetters(s: string): number {
      let ans = 0;
      const n = s.length;
      for (let i = 0; i < n; ) {
          let j = i;
          let cnt = 0;
          while (j < n && s[j] === s[i]) {
              ++j;
              ans += ++cnt;
          }
          i = j;
      }
      return ans;
  }
  
  

• class Solution {
      public int countLetters(String s) {
          int ans = 0;
          int i = 0, n = s.length();
          while (i < n) {
              int j = i;
              int cnt = 0;
              while (j < n && s.charAt(j) == s.charAt(i)) {
                  ++j;
                  ans += ++cnt;
              }
              i = j;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int countLetters(string s) {
          int ans = 0;
          int i = 0, n = s.size();
          while (i < n) {
              int j = i;
              int cnt = 0;
              while (j < n && s[j] == s[i]) {
                  ++j;
                  ans += ++cnt;
              }
              i = j;
          }
          return ans;
      }
  };
  

• class Solution:
      def countLetters(self, s: str) -> int:
          ans = 0
          i, n = 0, len(s)
          while i < n:
              j = i
              cnt = 0
              while j < n and s[j] == s[i]:
                  j += 1
                  cnt += 1
                  ans += cnt
              i = j
          return ans
  
  

• func countLetters(s string) (ans int) {
  	i, n := 0, len(s)
  	for i < n {
  		j := i
  		cnt := 0
  		for j < n && s[j] == s[i] {
  			j++
  			cnt++
  			ans += cnt
  		}
  		i = j
  	}
  	return
  }
  

All Problems

All Solutions