tags: [‘中等’,’贪心’,’字符串’,’力扣’]

题目

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。

你可以在 text 中任意位置插入 一个 字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。

请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。

子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。

示例 1：

  1. 输入：text = "abdcdbc", pattern = "ac"
  2. 输出：4
  3. 解释：
  4. 如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = 'a' ，那么我们得到 "abadcdbc" 。那么 "ac" 作为子序列出现 4 次。
  5. 其他得到 4 个 "ac" 子序列的方案还有 "aabdcdbc" 和 "abdacdbc" 。
  6. 但是，"abdcadbc" ，"abdccdbc" 和 "abdcdbcc" 这些字符串虽然是可行的插入方案，但是只出现了 3 次 "ac" 子序列，所以不是最优解。
  7. 可以证明插入一个字符后，无法得到超过 4 个 "ac" 子序列。

示例 2：

  1. 输入：text = "aabb", pattern = "ab"
  2. 输出：6
  3. 解释：
  4. 可以得到 6 个 "ab" 子序列的部分方案为 "aaabb" ，"aaabb" 和 "aabbb" 。

https://leetcode.cn/problems/maximize-number-of-subsequences-in-a-string/

初次分析

先将这道题拆解，划分为两个小问题：

  • 将 pattern[0] 插入到 text 中，使得 text 中最多包含多少个等于 pattern 的子序列。
  • 将 pattern[1] 插入到 text 中，使得 text 中最多包含多少个等于 pattern 的子序列。

两个子问题的答案取最大值即可。

接下来问题来了，怎么求一个字符串内包含指定字符串的子序列呢？

因为一旦解决这个问题，尝试不同的插入位置，即可算出题目的最终答案。

分析一下求子序列这个问题：例如abac，求ac子序列有多少个，怎么算？

首先明确，子序列是原字符串删除若干字符之后，剩下的字符按顺序组成的。

那么是不是可以这么理解，从原字符串中按照顺序挑选子序列长度的字符，看是否和预期的子序列相等？

嗯？好像是诶！

那么怎么遍历出所有的情况呢？直接看代码！

v1-暴力

  1. package main
  3. func maximumSubsequenceCount(text string, pattern string) int64 {
  4.     if len(pattern) < 2 {
  5.         return 0
  6.     }
  8.     // 尝试在text中插入不同位置的字符1
  9.     tmpText := text
  10.     tmpPatternInsert1 := make([]string, 0)
  11.     for i := 0; i <= len(text); i++ {
  12.         tmpText = text[:i] + pattern[0:1] + text[i:]
  13.         tmpPatternInsert1 = append(tmpPatternInsert1, tmpText)
  14.     }
  16.     // 计算1的子序列中为pattern的最大数量
  17.     maximumSubsequenceCount1 := int64(0)
  18.     for _, v := range tmpPatternInsert1 {
  19.         tmpPattern := genSubSeq(v, len(pattern), pattern)
  20.         tmpMax := int64(0)
  21.         for _, v := range tmpPattern {
  22.             if v == pattern {
  23.                 tmpMax++
  24.             }
  25.         }
  26.         if tmpMax > maximumSubsequenceCount1 {
  27.             maximumSubsequenceCount1 = tmpMax
  28.         }
  29.     }
  31.     // 尝试在text中插入不同位置的字符2
  32.     tmpText = text
  33.     tmpPatternInsert2 := make([]string, 0)
  34.     for i := 0; i <= len(text); i++ {
  35.         tmpText = text[:i] + pattern[1:] + text[i:]
  36.         tmpPatternInsert2 = append(tmpPatternInsert2, tmpText)
  37.     }
  38.     // 计算2的子序列中为pattern的最大数量
  39.     maximumSubsequenceCount2 := int64(0)
  40.     for _, v := range tmpPatternInsert2 {
  41.         tmpMax := int64(0)
  42.         tmpPattern := genSubSeq(v, len(pattern), pattern)
  43.         for _, v := range tmpPattern {
  44.             if v == pattern {
  45.                 tmpMax++
  46.             }
  47.         }
  48.         if tmpMax > maximumSubsequenceCount2 {
  49.             maximumSubsequenceCount2 = tmpMax
  50.         }
  51.     }
  53.     // 返回最大值
  54.     if maximumSubsequenceCount1 > maximumSubsequenceCount2 {
  55.         return maximumSubsequenceCount1
  56.     } else {
  57.         return maximumSubsequenceCount2
  58.     }
  60. }
  62. // 给定字符串，算出它的所有子序列组成
  63. func genSubSeq(text string, subLen int, pattern string) []string {
  65.     res := make([]string, 0)
  67.     for i := 0; i < len(text); i++ {
  68.         tmpChar := string(text[i])
  70.         // 如果长度不可能够，直接continue
  71.         if i+subLen > len(text) {
  72.             continue
  73.         }
  75.         // 如果首字母不符合，直接continue
  76.         if text[i] != pattern[0] {
  77.             continue
  78.         }
  80.         tmpRes := fetchStr(text, i+1, subLen-1, pattern)
  81.         for _, v := range tmpRes {
  82.             // 长度
  83.             if len(tmpChar)+len(v) != subLen {
  84.                 continue
  85.             }
  86.             res = append(res, tmpChar+v)
  87.         }
  88.     }
  89.     return res
  90. }
  92. func fetchStr(text string, left int, resLen int, pattern string) []string {
  93.     if resLen == 0 || left >= len(text) {
  94.         return nil
  95.     }
  97.     res := make([]string, 0)
  98.     for i := left; i < len(text); i++ {
  99.         tmpChar := string(text[i])
  101.         // 当前字母不符合指定下标的字符串，直接continue
  102.         if text[i] != pattern[1] {
  103.             continue
  104.         }
  106.         // 下一个字符的数据组
  107.         tmpRes := fetchStr(text, i+1, resLen-1, pattern)
  109.         if len(tmpRes) == 0 {
  110.             res = append(res, tmpChar)
  111.         } else {
  112.             for _, v := range tmpRes {
  113.                 res = append(res, tmpChar+v)
  114.             }
  115.         }
  116.     }
  117.     return res
  118. }

优化思路

可惜，暴力法的计算逻辑太多了。

运行之后在部分用例上超时了，这是因为使用递归方式，直接暴力计算，造成了大量重复计算。

我们在仔细想想这个问题。

我们真的需要考虑插入的所有的情况吗？

真的需要吗？

我们是不是只需要考虑将字符串插入首、尾两种情况呢？

因为这两种情况，才可能出现最大的子序列数。

v2-特殊情况

只需要改动这个地方，即只考虑首位情况。

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

很遗憾，最后还是超时了。

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

贪心算法

再一次思考，这个问题可不可以更简单？

遍历字符串，并且同时统计两个字符出现的频数。如果遇见 pattern[1]，就可以和前面出现过的 pattern[0] 组成子序列。

然后我们插入字符：

  • 如果加上 pattern[0]， 就加在字符串开头，与字符串中的 pattern[1] 组成新的子序列。
  • 如果加上 pattern[1]， 就加在字符串结尾，与字符串中的 pattern[0] 组成新的子序列。

最终新增的子字符串数量为两个字符频数的最大值，加到结果中并返回。

v3-贪心

  1. func maximumSubsequenceCount(text string, pattern string) int64 {
  2.     var res, cnt1, cnt2 int64
  3.     for _, c := range text {
  4.         if byte(c) == pattern[1] {
  5.             res += cnt1
  6.             cnt2++
  7.         }
  8.         if byte(c) == pattern[0] {
  9.             cnt1++
  10.         }
  11.     }
  12.     if cnt1 > cnt2 {
  13.         return res + cnt1
  14.     }
  15.     return res + cnt2
  16. }

思考

如果 pattern 的长度是 3 呢？

是 m 呢？