leetcode1898_go_可移除字符的最大数目

题目

给你两个字符串 s 和 p ，其中 p 是 s 的一个子序列。

同时，给你一个元素互不相同且下标从 0 开始计数的整数数组 removable ，

该数组是 s 中下标的一个子集（s 的下标也从 0 开始计数）。

请你找出一个整数 k（0 <= k <= removable.length），选出 removable 中的前 k 个下标，

然后从 s 中移除这些下标对应的 k 个字符。整数 k 需满足：在执行完上述步骤后， p 仍然是 s 的一个子序列。

更正式的解释是，对于每个 0 <= i < k ，先标记出位于 s[removable[i]] 的字符，

接着移除所有标记过的字符，然后检查 p 是否仍然是 s 的一个子序列。

返回你可以找出的最大 k ，满足在移除字符后 p 仍然是 s 的一个子序列。

字符串的一个子序列是一个由原字符串生成的新字符串，

生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。

示例 1：输入：s = "abcacb", p = "ab", removable = [3,1,0] 输出：2

解释：在移除下标 3 和 1 对应的字符后，"abcacb" 变成 "accb" 。

"ab" 是 "accb" 的一个子序列。

如果移除下标 3、1 和 0 对应的字符后，"abcacb" 变成 "ccb" ，那么 "ab" 就不再是 s 的一个子序列。

因此，最大的 k 是 2 。

示例 2：输入：s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6] 输出：1

解释：在移除下标 3 对应的字符后，"abcbddddd" 变成 "abcddddd" 。

"abcd" 是 "abcddddd" 的一个子序列。

示例 3：输入：s = "abcab", p = "abc", removable = [0,1,2,3,4] 输出：0

解释：如果移除数组 removable 的第一个下标，"abc" 就不再是 s 的一个子序列。

提示：1 <= p.length <= s.length <= 105

0 <= removable.length < s.length

0 <= removable[i] < s.length

p 是 s 的一个子字符串

s 和 p 都由小写英文字母组成

removable 中的元素互不相同

解题思路分析

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

func maximumRemovals(s string, p string, removable []int) int {
   n := len(removable)
   left, right := 0, n
   for left < right {
      mid := left + (right-left)/2
      if judge(s, p, removable, mid) == true {
         left = mid + 1
      } else {
         right = mid
      }
   }
   return left
}

// leetcode 392.判断子序列
func judge(s string, p string, removable []int, index int) bool {
   m := make(map[int]bool)
   for i := 0; i < len(removable[:index+1]); i++ {
      m[removable[i]] = true
   }
   i, j := 0, 0
   for i < len(p) && j < len(s) {
      if p[i] == s[j] && m[j] == false {
         i++
      }
      j++
   }
   return i == len(p)
}

2、二分查找；时间复杂度O(nlog(n))，空间复杂度O(n)

func maximumRemovals(s string, p string, removable []int) int {
   n := len(removable)
   left, right := 0, n+1
   for left < right {
      mid := left + (right-left)/2
      if judge(s, p, removable, mid) == true {
         left = mid + 1
      } else {
         right = mid
      }
   }
   return left - 1
}

// leetcode 392.判断子序列
func judge(s string, p string, removable []int, index int) bool {
   m := make(map[int]bool)
   for i := 0; i < len(removable[:index]); i++ {
      m[removable[i]] = true
   }
   i, j := 0, 0
   for i < len(p) && j < len(s) {
      if p[i] == s[j] && m[j] == false {
         i++
      }
      j++
   }
   return i == len(p)
}

3、内置函数；时间复杂度O(nlog(n))，空间复杂度O(n)

func maximumRemovals(s string, p string, removable []int) int {
   n := len(removable)
   return sort.Search(n, func(index int) bool {
      m := make(map[int]bool)
      for i := 0; i < len(removable[:index+1]); i++ {
         m[removable[i]] = true
      }
      i, j := 0, 0
      for i < len(p) && j < len(s) {
         if p[i] == s[j] && m[j] == false {
            i++
         }
         j++
      }
      return i != len(p)
   })
}