Question

1358. 包含所有三种字符的子字符串数目

English Version

题目描述

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

 

示例 1：

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为_ "_abc_", "_abca_", "_abcab_", "_abcabc_", "_bca_", "_bcab_", "_bcabc_", "_cab_", "_cabc_" _和_ "_abc_" _(相同字符串算多次)_。_

示例 2：

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为_ "_aaacb_", "_aacb_" _和_ "_acb_" 。_

示例 3：

输入：s = "abc"
输出：1

 

提示：

• 3 <= s.length <= 5 x 10^4
• s 只包含字符 a，b 和 c 。

解法

方法一：一次遍历

我们用一个长度为 $3$ 的数组 $d$ 记录三种字符最近一次出现的位置，初始时均为 $-1$。

遍历字符串 $s$，对于当前位置 $i$，我们先更新 $d[s[i]]=i$，然后合法的字符串个数为 $\min(d[0], d[1], d[2]) + 1$，累加到答案中。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $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
}