最多提取子串数目
最多提取子串数目
题目给定由[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
的字符串
行末无多余空格
备注
无需验证输入格式和输入数据合法性
示例一
输入：
badc
bac
输出
1
def result(a, b):
# 其中 a可能存在重复字母
# B 不会存在重复字母
# idxs 对象记录字符串 b 中每个字符的索引
idxs = {} # bac{b:0, a:1, c:2}
for i in range(len(b)):
idxs[b[i]] = i # 题目说了，b上面是没有重复的元素的。
# count 对象用于记录遍历字符串 a 每个字符串过程中，统计到的符合顺序要求的字符串b中字符出现次数
count = [0] * len(b)
print(idxs) # 映射B字符串和位置
print(count)
for c in a: #遍历
# 取的到值就去得到。取不到就位None
idx = idxs.get(c) # idx的值只可能为012，分别对应的bac
# 取到值，要么为0最大的，就只管加，或者count[idx]<count[idx-1]
if idx is not None and (idx == 0 or count[idx]<count[idx-1]):
count[idx] += 1
print(count)
return count[-1]
a = input()
b = input()
print(a)
print(b)
print(result(a,b))