Question

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)$.

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

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

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

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
}

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

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

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

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
}