leetcode
leetcode 1901 ~ 1950
字符串中最多数目的子序列

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

难度:

标签:

题目描述

代码结果

运行时间: 82 ms, 内存: 16.6 MB


/*
题目思路:
1. 使用流的方式,计算当前字符串中 pattern[0] 和 pattern[1] 出现的次数。
2. 通过流的 map 和 reduce 操作,计算插入后 pattern 出现的次数。
*/

import java.util.stream.IntStream;

public class Solution {
    public int maxPatternSubsequence(String text, String pattern) {
        char p1 = pattern.charAt(0), p2 = pattern.charAt(1);
        int count1 = 0, count2 = 0;

        count2 = (int) text.chars().filter(c -> c == p2).count();

        // 使用流计算最大 pattern 出现次数
        int maxCount = IntStream.range(0, text.length())
                .map(i -> {
                    if (text.charAt(i) == p1) {
                        count1++;
                    } else if (text.charAt(i) == p2) {
                        count2--;
                    }
                    return count1 + count2;
                })
                .max()
                .orElse(count1 + count2);

        // 考虑插入到字符串末尾的情况
        maxCount = Math.max(maxCount, count1 + count2);

        return maxCount;
    }
}

解释

方法:

该题解通过遍历字符串text,统计模式pattern中第一个字符x和第二个字符y的出现次数以及可以形成的子序列数量。特别注意的是,若x和y相同,即pattern由两个相同的字符组成,其处理逻辑不同:直接计算所有可能位置插入新字符后的子序列数量。主要步骤为:1. 如果x和y相同,计算插入后的字符数量,利用组合公式计算可形成的子序列数。2. 如果x和y不同,遍历text,每次遇到x,增加cntx;遇到y时,将cntx累加到结果ret中,并增加cnty。最后,考虑插入一个字符后,取cntx和cnty中的最大值加到ret中,这反映了通过插入一个字符(x或y)可以额外增加的子序列数量。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,如何确保在遍历text时统计的子序列不会重复计数?
在遍历过程中,每次遇到字符y时,仅将当前字符x的计数(cntx)累加到结果(ret)中。这种方法确保每个y只与其前面的所有x形成子序列,避免了重复计数。
🦆
算法对于插入字符的位置是如何考虑的,是否有特定的最优位置或是随意插入就可以?
算法通过在最终结果中添加max(cntx, cnty)来考虑插入一个字符x或y后可能增加的最大子序列数。这种方法表明,插入的最优位置不是固定的,而是可以在任何位置插入新字符,以最大化可能的子序列数量。
🦆
当pattern由两个相同字符组成时,为什么使用组合数公式`(cnt - 1) * cnt // 2`来计算子序列总数?
当pattern由两个相同字符组成时,每个字符都可以与之前出现的相同字符形成一个有效的子序列。使用组合数公式是为了计算从text中选取两个相同字符进行配对的所有可能方式。`(cnt - 1) * cnt // 2`计算的是从cnt个字符中任选两个形成子序列的组合数。
🦆
在处理x和y不同的情况时,为什么最后选择`max(cntx, cnty)`来计算通过插入一个字符可能增加的子序列数?
选择`max(cntx, cnty)`是为了找出通过插入一个额外的字符(x或y)可以带来的最大增益。如果插入x,可能会与所有现有的y形成新的子序列;同理,插入y时,每个新的y都可以与所有已存在的x配对。因此,选择两者中的最大值,以最大化新增子序列的数量。

相关问题