Medium

题目描述

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

你可以在 text 中任意位置恰好添加 pattern[0] 或 pattern[1] 中的一个字符。注意，这个字符可以添加在 text 的开头或者结尾。

返回添加一个字符后，pattern 作为 text 的子序列出现的最大次数。

子序列是指可以从另一个字符串删除某些字符（也可以不删除）但不改变其余字符顺序得到的字符串。

示例 1：

输入：text = "abdcdbc", pattern = "ac"
输出：4
解释：
如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = 'a'，我们得到 "abadcdbc"。现在，"ac" 作为子序列出现了 4 次。
添加一个字符后能得到 4 个子序列 "ac" 的其他字符串有 "aabdcdbc" 和 "abdacdbc"。
然而，诸如 "abdcadbc"、"abdccdbc" 和 "abdcdbcc" 这样的字符串虽然可以得到，但只有 3 个子序列 "ac"，因此不是最优的。
可以证明添加一个字符后不可能得到超过 4 个子序列 "ac"。

示例 2：

输入：text = "aabb", pattern = "ab"
输出：6
解释：
从 text 可以得到并且有 6 个子序列 "ab" 的一些字符串是 "aaabb"、"aaabb" 和 "aabbb"。

提示：

  • 1 <= text.length <= 10^5
  • pattern.length == 2
  • text 和 pattern 只包含小写英文字母

解题思路

这道题的核心思路是贪心策略。我们需要分别考虑添加 pattern[0] 和 pattern[1] 两种情况，然后取最大值。

基本思路：

  1. 添加 pattern[0]的情况：为了最大化子序列数量，我们应该将 pattern[0] 添加到最前面。这样新加的字符可以与后面所有的 pattern[1] 组成新的子序列。

  2. 添加 pattern[1]的情况：类似地，我们应该将 pattern[1] 添加到最后面，让前面所有的 pattern[0] 都能与新加的字符组成子序列。

具体算法：

对于每种情况，我们需要：

  • 统计原字符串中 pattern[0] 和 pattern[1] 的出现次数
  • 计算原字符串中已有的子序列数量
  • 根据添加位置计算新增的子序列数量

计算子序列数量的方法： 从左到右遍历字符串，维护 pattern[0] 的累计数量，每遇到一个 pattern[1]，就将当前 pattern[0] 的数量加到结果中。

需要注意 pattern[0] 和 pattern[1] 相同的特殊情况，此时任选位置添加一个字符即可。

代码实现

class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        char p0 = pattern[0], p1 = pattern[1];
        
        // 特殊情况：pattern[0] == pattern[1]
        if (p0 == p1) {
            long long count = 0;
            for (char c : text) {
                if (c == p0) count++;
            }
            return count * (count + 1) / 2;
        }
        
        // 情况1：在开头添加 pattern[0]
        long long count1 = 0, p0_count = 1; // 开头已添加一个 p0
        for (char c : text) {
            if (c == p1) {
                count1 += p0_count;
            } else if (c == p0) {
                p0_count++;
            }
        }
        
        // 情况2：在结尾添加 pattern[1]
        long long count2 = 0, p0_count2 = 0;
        for (char c : text) {
            if (c == p1) {
                count2 += p0_count2;
            } else if (c == p0) {
                p0_count2++;
            }
        }
        count2 += p0_count2; // 结尾添加的 p1 与所有 p0 组成子序列
        
        return max(count1, count2);
    }
};

class Solution:
    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
        p0, p1 = pattern[0], pattern[1]
        
        # 特殊情况：pattern[0] == pattern[1]
        if p0 == p1:
            count = text.count(p0)
            return count * (count + 1) // 2
        
        # 情况1：在开头添加 pattern[0]
        count1 = 0
        p0_count = 1  # 开头已添加一个 p0
        for c in text:
            if c == p1:
                count1 += p0_count
            elif c == p0:
                p0_count += 1
        
        # 情况2：在结尾添加 pattern[1]
        count2 = 0
        p0_count2 = 0
        for c in text:
            if c == p1:
                count2 += p0_count2
            elif c == p0:
                p0_count2 += 1
        count2 += p0_count2  # 结尾添加的 p1 与所有 p0 组成子序列
        
        return max(count1, count2)

public class Solution {
    public long MaximumSubsequenceCount(string text, string pattern) {
        char p0 = pattern[0], p1 = pattern[1];
        
        // 特殊情况：pattern[0] == pattern[1]
        if (p0 == p1) {
            long count = 0;
            foreach (char c in text) {
                if (c == p0) count++;
            }
            return count * (count + 1) / 2;
        }
        
        // 情况1：在开头添加 pattern[0]
        long count1 = 0, p0Count = 1; // 开头已添加一个 p0
        foreach (char c in text) {
            if (c == p1) {
                count1 += p0Count;
            } else if (c == p0) {
                p0Count++;
            }
        }
        
        // 情况2：在结尾添加 pattern[1]
        long count2 = 0, p0Count2 = 0;
        foreach (char c in text) {
            if (c == p1) {
                count2 += p0Count2;
            } else if (c == p0) {
                p0Count2++;
            }
        }
        count2 += p0Count2; // 结尾添加的 p1 与所有 p0 组成子序列
        
        return Math.Max(count1, count2);
    }
}

/**
 * @param {string} text
 * @param {string} pattern
 * @return {number}
 */
var maximumSubsequenceCount = function(text, pattern) {
    const [a, b] = pattern;
    
    if (a === b) {
        const count = text.split('').filter(c => c === a).length + 1;
        return count * (count - 1) / 2;
    }
    
    let countA = 0, countB = 0, subsequences = 0;
    
    for (const char of text) {
        if (char === a) {
            countA++;
        } else if (char === b) {
            subsequences += countA;
            countB++;
        }
    }
    
    return subsequences + Math.max(countA, countB);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)其中 n 是字符串 text 的长度，需要遍历字符串两次
空间复杂度O(1)只使用常数额外空间

相关题目