leetcode1930_go_长度为3的不同回文子序列

题目

给你一个字符串 s ，返回 s 中长度为 3 的不同回文子序列的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文是正着读和反着读一样的字符串。

子序列是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列。

示例 1：输入：s = "aabca"输出：3

解释：长度为 3 的 3 个回文子序列分别是：

- "aba" ("aabca" 的子序列)

- "aaa" ("aabca" 的子序列)

- "aca" ("aabca" 的子序列)

示例 2：输入：s = "adc"输出：0

解释："adc" 不存在长度为 3 的回文子序列。

示例 3：输入：s = "bbcbaba" 输出：4

解释：长度为 3 的 4 个回文子序列分别是：

- "bbb" ("bbcbaba" 的子序列)

- "bcb" ("bbcbaba" 的子序列)

- "bab" ("bbcbaba" 的子序列)

- "aba" ("bbcbaba" 的子序列)

提示：3 <= s.length <= 105

s 仅由小写英文字母组成

解题思路分析

1、遍历；时间复杂度O(n)，空间复杂度O(n)

func countPalindromicSubsequence(s string) int {
   n := len(s)
   arr := [26][]int{}
   for i := 0; i < n; i++ {
      index := int(s[i] - 'a')
      arr[index] = append(arr[index], i)
   }
   m := make(map[string]bool)
   for i := 0; i < 26; i++ { // 枚举2边字符
      if len(arr[i]) <= 1 {
         continue
      }
      left, right := arr[i][0], arr[i][len(arr[i])-1]
      for j := 0; j < 26; j++ {
         if len(arr[j]) == 0 {
            continue
         }
         if i == j && len(arr[i]) > 2 {
            m[fmt.Sprintf("%d,%d,%d", i, i, i)] = true
            continue
         }
         flag := false
         for k := 0; k < len(arr[j]); k++ {
            if left < arr[j][k] && arr[j][k] < right {
               flag = true
               break
            }
         }
         if flag == true {
            m[fmt.Sprintf("%d,%d,%d", i, j, i)] = true
         }
      }
   }
   return len(m)
}

2、遍历；时间复杂度O(n)，空间复杂度O(1)

func countPalindromicSubsequence(s string) int {
   n := len(s)
   res := 0
   for i := 0; i < 26; i++ { // 枚举2边字符
      left, right := 0, n-1
      for left < n && s[left] != byte(i+'a') {
         left++
      }
      for right >= 0 && s[right] != byte(i+'a') {
         right--
      }
      if left+2 > right {
         continue
      }
      m := make(map[byte]int)
      for k := left + 1; k < right; k++ {
         m[s[k]] = 1
      }
      res = res + len(m)
   }
   return res
}

3、遍历+位运算；时间复杂度O(n)，空间复杂度O(n)

func countPalindromicSubsequence(s string) int {
   n := len(s)
   res := 0
   pre, suf := make([]int, n+1), make([]int, n+1)
   arr := make([]int, 26)
   for i := 0; i < n; i++ {
      pre[i+1] = pre[i] | (1 << int(s[i]-'a'))
   }
   for i := n - 1; i >= 0; i-- {
      suf[i] = suf[i+1] | (1 << int(s[i]-'a'))
   }
   for i := 1; i < n-1; i++ {
      index := int(s[i] - 'a')
      arr[index] = arr[index] | (pre[i] & suf[i+1])
   }

   for i := 0; i < 26; i++ {
      res = res + bits.OnesCount(uint(arr[i]))
   }
   return res
}