Question

1358. Number of Substrings Containing All Three Characters

中文文档

Description

Given a string s consisting only of characters _a_, _b_ and _c_.

Return the number of substrings containing at least one occurrence of all these characters _a_, _b_ and _c_.

 

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters _a_, _b_ and _c are "_abc_", "_abca_", "_abcab_", "_abcabc_", "_bca_", "_bcab_", "_bcabc_", "_cab_", "_cabc_" _and_ "_abc_" _(again)_. _

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters _a_, _b_ and _c are "_aaacb_", "_aacb_" _and_ "_acb_".__ _

Example 3:

Input: s = "abc"
Output: 1

 

Constraints:

• 3 <= s.length <= 5 x 10^4
• s only consists of _a_, _b_ or _c _characters.

Solutions

Solution 1: Single Pass

We use an array $d$ of length $3$ to record the most recent occurrence of the three characters, initially all set to $-1$.

We traverse the string $s$. For the current position $i$, we first update $d[s[i]]=i$, then the number of valid strings is $\min(d[0], d[1], d[2]) + 1$, which is accumulated to the answer.

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

class Solution:
  def numberOfSubstrings(self, s: str) -> int:
    d = {"a": -1, "b": -1, "c": -1}
    ans = 0
    for i, c in enumerate(s):
      d[c] = i
      ans += min(d["a"], d["b"], d["c"]) + 1
    return ans

class Solution {
  public int numberOfSubstrings(String s) {
    int[] d = new int[] {-1, -1, -1};
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      d[c - 'a'] = i;
      ans += Math.min(d[0], Math.min(d[1], d[2])) + 1;
    }
    return ans;
  }
}

class Solution {
public:
  int numberOfSubstrings(string s) {
    int d[3] = {-1, -1, -1};
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
      d[s[i] - 'a'] = i;
      ans += min(d[0], min(d[1], d[2])) + 1;
    }
    return ans;
  }
};

func numberOfSubstrings(s string) (ans int) {
  d := [3]int{-1, -1, -1}
  for i, c := range s {
    d[c-'a'] = i
    ans += min(d[0], min(d[1], d[2])) + 1
  }
  return
}