Categorygithub.com/szhou12/leetcode-goleetcode2565-Subsequence-With-the-Minimum-Score
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
1
Dependents
0

# README

2565. Subsequence With the Minimum Score

Solution idea

Binary Search 猜答案 + 3-Pass

Note: 为了容易理解，这里提及的 [x:y] 都是左闭右闭

要点总结

  1. 此题需要对题干进行翻译。翻译题目: 删除t的一个subarray (甭管内部怎么删的，删了几个char), 使得剩下的chars能组成s的subseq
    • 题目中的score定义就是subarray length. Minimum score = minimun length of subarray
  2. 根据翻译, 可以归纳一个规律: 删除的这个subarray越长, 剩下的chars越容易组成s的subseq (eg. 最极端的例子是t删除到什么都不剩了，一个空串肯定是s的subseq) --> 单调性 --> 暗示可以用 binary search 猜答案
  3. 圈定一个区间作为删除的subarray, 不需要在它内部额外操作, 直接整个删掉
  4. 作图:
t:   x x x  {y y y}  z z z
         i           j

根据上图, t被圈出的subarray {y y y} 把t 分成L, M, R三段. 显然, 可以使用 3-Pass 来解

使用两个DP思想的arrays来分别记录L段和R段的信息: left[], right[]

物理意义

Note: m=len(s), n=len(t)

left[i] := Rightmost index r for the shortest prefix of s (i.e. s[0:r]) containing t[0:i]
right[j] := Leftmost index l for the shortest suffix of s (ie. s[l:m-1]) containing t[j:n-1]

  • 翻译一下

    • left[] 记录 s的前缀 中 右端点r 的index信息
    • right[] 记录 s的后缀 中 左端点l 的index信息

  • 物理意义的几个要点:

    • left[], right[] 记录的是(滑窗)端点的index信息, 不是长度或者其他什么物理量
    • What is prefix of s & suffix of s?
      • prefix of s: s的前缀 指的是 s[0:r], 从开始index到r框住的区域, r不断往后延伸直到结尾index
      • suffix of s: s的后缀 指的是 s[l:m-1], 从l到结尾index框住的区域, l不断向前延伸直到开始index
    • Why shortest?
      • left[i], right[j] 寻找的是最小可行解 (下限), 最大可行解很容易想到就是s整个字符串; 同时, 也是greedy/sliding window的思想, 当计算下一个 left[i+1]的时候, r可以继承上一次的位置继续延伸，避免重复解或者漏解 (shortest相当于起到一个限制的作用, 每一轮只要刚刚好就收手, 进行下一轮)
    • 找不到的情况
      • 如果 t[0:i] 无法成为subseq (i.e. 包含了s没有的char), 则 left[i] = MaxInt (谨遵物理意义, MaxInt表示s前缀的右端点r不论怎么向后延伸, 即使伸到无限远处都无法包含t[0:i])
        • left[i] = m 也行, 表示前缀的右端点r无法到达的地方/无解
      • 如果 t[j:n-1] 无法成为subseq (i.e. 包含了s没有的char), 则 right[j] = MinInt (谨遵物理意义, MinInt表示s后缀的左端点l不论怎么向前延伸, 即使伸到无限小处都无法包含t[j:n-1])
        • right[j] = -1 也行, 表示后缀的左端点l无法到达的地方/无解

如何用Binary Search猜答案

Note: m=len(s), n=len(t)

  • 一旦建立好 left[] 和 right[], 就可以用Binary Search猜答案

  • 猜什么?

    • 物理量: Score = t中要删除的subarray的长度

  • 怎么猜？

    • sliding window: 假设猜score = mid长度, 就用长度为mid的滑窗在t上滑一遍
    • 判定条件: 滑窗滑动过程中, 只要找到任一个位置使得 s前缀的右端点 与 s后缀的左端点 不重叠, 就说明当前mid是一个合法解
      • sliding window = [i:i+score-1], 不重叠意味着 left[i-1] < right[i+score]
      • 细节: 注意sliding window 分别顶在t最左边和最右边的时候, left[i-1] < right[i+score]会发生越界. 这是因为: 顶在t最左边时, 不需要看left[], 只用看right[]; 顶在t最右边时, 不需要看right[], 只用看left[]:
        • 顶在t最左边时: right[0+score]有解, mid就是一个合法解
        • 顶在t最右边时: left[n-score-1]有解, mid就是一个合法解

  • 如何收敛?

    • 二分搜值最小可搜值: 0 (物理意义: t一个字符不删)
    • 二分搜值最小可搜值: n (物理意义: t全删了)
    • 当前mid判定为合法解时, 说明它可以是一个解, 因为题目要求 Minimum Score, 再试试小一点的值, 右挡板=mid
    • 当前mid判定为不合法时, 说明它一定不是一个解, 左挡板=mid+1

  • 答案一定存在吗?

    • 一定存在, 大不了就把t全删掉。所以二分搜值收敛解即是答案, 不用post-processing

代码整体结构总结

Step 1: 构造left[]: s一个指针, t一个指针, 两个指针不停往右走, 记录"沿途风景"
Step 2: 构造right[]: s一个指针, t一个指针, 两个指针不停往左走, 记录"沿途风景"
Step 3: 二分搜值搜索t中可裁剪的subarray的长度

Time complexity = $O(n) + O(n) + O(n*\log D) = O(n*\log D)$ where $D = $ the length of t (ie. $D = |t|-0$)

Resource

【每日一题】LeetCode 2565. Subsequence With the Minimum Score