【华为OD机试2023】最多提取子串数目Python

题目描述：

给定由 [a-z] 26个英文小写字母组成的字符串A和B，其中A中可能存在重复字母，B中不会存在重复字母

现从字符串A中按规则挑选一些字母，可以组成字符串B。

挑选规则如下：

1）  同一个位置的字母只能被挑选一次

2）  被挑选字母的相对先后顺序不能改变

求最多可以同时从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("abc")

示例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")

解题思路：

两个指针，i指向a[0]，j指向b[0]，如果两者相等，i和j均加一；否则i加一。如此循环直到j超出了b的长度（a中可以找到一个字符串b）或者i超出了a的长度（搜完一遍还是没能从a中找到字符串b），前者继续开启循环，后者退出循环

a=list(input())
b=list(input())
i=0
j=0
count=0
sum=0
temp=[]
while True:
    if count <len(b):
        if i<len(a):
            if a[i]==b[j]:
                temp.append(i)
                i+=1
                j+=1
                count+=1
            else:
                i+=1
        else:
            break
    else:
        for num in temp:
            a[num]=0
        temp.clear()
        sum+=1
        count=0
print(sum)