↓Skip to main content
  1. Posts/

LeetCode-2207 字符串中最多数目的子序列

·1 min·
Table of Contents

LeetCode-2207 字符串中最多数目的子序列 #

Solution 1 #

计算初始数量 + 插入带来的增益.

代码如下:

class Solution:
    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
        n = len(text)
        pre0, pre1 = [0 for _ in range(n)], [0 for _ in range(n)]
        ans = 0

        for i in range(0, n):
            if text[i] == pattern[1]:
                ans += pre0[i - 1]
            pre0[i] = (pre0[i - 1] if i > 0 else 0) + (text[i] == pattern[0])
            pre1[i] = (pre1[i - 1] if i > 0 else 0) + (text[i] == pattern[1])
            
        ans += max([max(
            pre1[n - 1] - (pre1[i - 1] if i > 0 else 0), # pat0
            pre0[i]) for i in range(n)]
        )
        return ans