题目

给你一个字符串 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 。

解题思路分析

1、前缀和+二分查找；时间复杂度O(nlog(n))，空间复杂度O(n)

func numberOfSubstrings(s string) int {
   res := 0
   n := len(s)
   arr := make([][3]int, n+1)
   for i := 0; i < n; i++ {
      for j := 0; j < 3; j++ {
         arr[i+1][j] = arr[i][j]
      }
      value := int(s[i] - 'a')
      arr[i+1][value]++
   }
   for i := 0; i < n; i++ {
      left := i + 1
      right := n
      index := -1
      for left <= right {
         mid := left + (right-left)/2
         if arr[mid][0] > arr[i][0] &&
            arr[mid][1] > arr[i][1] &&
            arr[mid][2] > arr[i][2] {
            right = mid - 1
            index = mid
         } else {
            left = mid + 1
         }
      }
      if index != -1 {
         res = res + n - index + 1
      }
   }
   return res
}

2、双指针；时间复杂度O(n)，空间复杂度O(1)

func numberOfSubstrings(s string) int {
   res := 0
   n := len(s)
   arr := [3]int{}
   left := 0
   right := -1
   var value int
   for left = 0; left < n; left++ {
      for right < n && (arr[0] == 0 || arr[1] == 0 || arr[2] == 0) {
         right++
         if right == n {
            break
         }
         value = int(s[right] - 'a')
         arr[value]++
      }
      res = res + n - right
      value = int(s[left] - 'a')
      arr[value]--
   }
   return res
}

3、双指针；时间复杂度O(n)，空间复杂度O(1)

func numberOfSubstrings(s string) int {
   res := 0
   n := len(s)
   arr := [3]int{}
   var value int
   i := 0
   for j := 0; j < n; j++ {
      value = int(s[j] - 'a')
      arr[value]++
      for arr[0] > 0 && arr[1] > 0 && arr[2] > 0 {
         res = res + n - j
         value = int(s[i] - 'a')
         arr[value]--
         i++
      }
   }
   return res
}

4、map；时间复杂度O(n)，空间复杂度O(1)

func numberOfSubstrings(s string) int {
   res := 0
   n := len(s)
   m := make(map[int]int)
   count := 0
   var value int
   i := 0
   for j := 0; j < n; j++ {
      value = int(s[j] - 'a')
      if m[value] == 0 {
         count++
      }
      m[value]++
      for count == 3 {
         res = res + n - j
         value = int(s[i] - 'a')
         m[value]--
         i++
         if m[value] == 0 {
            count--
         }
      }
   }
   return res
}

总结

Medium题目，双指针题目，类似的题目还有leetcode 992.K个不同整数的子数组