题目简述

给定两个字符串 A 和 B，其中 A 是由 [a-z] 中小写字母组成且可能有重复字符，而 B 是由 [a-z] 中小写字母组成且不含重复字符。要求从字符串 A 中按一定规则挑选字符以组成字符串 B，并计算最多能从 A 中同时挑选出多少组字符串 B。

挑选规则：

1. 同一个位置的字符只能挑选一次。
2. 挑选出的字符相对顺序不能改变。

解题思路

1. 问题拆解

• 核心问题是从字符串 A 中找到 B 的子序列。
• 为了满足子序列的定义，字符顺序不能打乱， B的字符不重复，因此可以使用贪心的方式：
  • 遍历字符串 A，找到 B 的每个字符依次出现的位置。

2. 实现步骤

• 使用一个哈希表 char_index 保存 B 中每个字符及其索引位置，方便快速判断某个字符是否属于 B。
• 使用一个数组 match_count 表示当前能够匹配到 B 的每一位的次数。
• 遍历字符串 A：
  • 如果当前字符属于 B，尝试将其放入对应位置，更新 match_count。
  • 如果某一位 B 已匹配完成，则将匹配推进到下一位。
• 最终统计 match_count 中最后一位的次数，这就是最多匹配 B 的组数。

3. 复杂度分析

• 时间复杂度：O(A.length + B.length)，其中哈希表建立需要 O(B.length)，遍历字符串 A 需要 O(A.length)。
• 空间复杂度：O(B.length)，用于存储哈希表和匹配状态数组。

代码实现

Python代码

# Python解法
A = input()  # 输入字符串A
B = input()  # 输入字符串B

n = len(B)
# char_index存储B中每个字符的位置索引
char_index = {B[i]: i for i in range(n)}
# match_count用于存储匹配到B每一位的次数
match_count = [ 0 for i in range(n+1)]

for i in A:
    if i not in char_index:  # 如果当前字符不在B中，跳过
        continue
    k = char_index[i]  # 获取字符i在B中的位置
    if k == 0:
        match_count[k + 1] += 1  # 如果是B的第一个字符，直接匹配
    elif match_count[k] > 0:
        match_count[k] -= 1  # 消耗前一位匹配的次数
        match_count[k + 1] += 1  # 当前位匹配次数加1

print(match_count[n])  # 输出能组成B的最大组数

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.nextLine();
        String B = sc.nextLine();

        int bLen = B.length();
        Map<Character, Integer> charIndex = new HashMap<>();
        for (int i = 0; i < bLen; i++) {
            charIndex.put(B.charAt(i), i); // 存储B中每个字符及其索引
        }

        int[] matchCount = new int[bLen + 1]; // 匹配计数
        for (char c : A.toCharArray()) {
            if (!charIndex.containsKey(c)) continue; // 如果当前字符不在B中，跳过
            int idx = charIndex.get(c);
            if (idx == 0) {
                matchCount[idx + 1] += 1; // 匹配B的第一个字符
            } else if (matchCount[idx] > 0) {
                matchCount[idx] -= 1; // 消耗前一位的匹配次数
                matchCount[idx + 1] += 1; // 当前位匹配次数加1
            }
        }

        System.out.println(matchCount[bLen]); // 输出能组成B的最大组数
    }
}

C++代码

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    string A, B;
    cin >> A >> B;

    int n = B.size();
    unordered_map<char, int> char_index;
    for (int i = 0; i < n; ++i) {
        char_index[B[i]] = i; // 将B中字符及其索引存入哈希表
    }

    int match_count[n + 1] = {0}; // 用于存储匹配到B每一位的次数
    for (char c : A) {
        if (char_index.find(c) == char_index.end()) continue; // 如果当前字符不在B中，跳过
        int k = char_index[c];
        if (k == 0) {
            match_count[k + 1] += 1; // 匹配B的第一个字符
        } else if (match_count[k] > 0) {
            match_count[k] -= 1; // 消耗前一位的匹配次数
            match_count[k + 1] += 1; // 当前位匹配次数加1
        }
    }

    cout << match_count[n] << endl; // 输出能组成B的最大组数
    return 0;
}

题目内容

给定 $[a-z]$，$26$ 个英文字母小写字符串组成的字符串 $A$ 和 $B$，其中 $A$ 可能存在重复字母，$B$ 不会存在重复字母，现从字符串 $A$ 中按规则挑选一些字母，可以组成字符串 $B$ 。

挑选规则如下：

同一个位置的字母只能挑选一次 被挑选字母的相对先后顺序不能被改变 求最多可以同时从 $A$ 中挑选多少组能组成 $B$ 的字符串。

输入描述

输入为 $2$ 行，第 $1$ 行输入字符串 $A$ ，第 $2$ 行输入字符串 $B$，行首行尾没有多余空格，其中：

$A、B$ 均由 $[a-z]$ $26$ 个英文小写字母组成

$0 < A.length < 100$，$A$ 中可能包含重复字母

$0 < B.length < 10$，$B$ 中不会出现重复字母

输出描述

输出 $1$ 行，包含 $1$ 个数字，表示最多可以同时从 $A$ 中挑选多少组能组成 $B$ 的字符串

行末没有多余空格

备注

无需验证输入格式和输入数据合法性

样例1

输入

badc
bac

输出

1

说明

从字符串 $A$（"$badc$"）中可以按字母相对先后顺序取出字符串 $B$（"$bac$"）

样例2

输入

badc
abc

输出

0

说明

从字符串 $A$（"$badc$"）中无法按字母相对先后顺序取出字符串 $B$（"$bac$"）

样例3

输入

aabbcxd
abcd

输出

1

说明

从字符串 $A$（"$aabbcxd$"）中挑选一组 $B$（"$abcd$"）后，$A$ 中剩余字符串为 "$abx$"，无法再挑选出 "$abcd$"

样例4

输入

ababcecfdc
abc

输出

2

说明

从按如下步骤（步骤不唯一），可以同时从字符串 $A$（"$ababcecfdc$"）中最多取出两个 $B$（"$abc$"），其中颜色标注的是每步提取的字母：

剩余的 "$efdc$" 无法继续提取 "$abc$"，结果为 $2$

样例5

输入

aaa
a

输出

3

说明

从字符串 $A$（"$aaa$"）中可以挑选出 $3$ 个字符串 $B$（"$a$"）