OD B卷【恢复数字序列】

题目：

对于一个连续正整数组成的序列，可以将其拼接成一个字符串，在将字符串里的部分字符打乱顺序。如序列8 9 10 11 12， 拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1，现给定一个按如上规则得到的打乱字符的字符串，将其还原成连续正整数序列，并输出序列中最小的数字。
输入描述：
输入一行，为打乱字符的字符串和正整数序列的长度，空格隔开，字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。
输出描述：
输出一个数字，为序列中最小的数字。

示例1
输入：
19801211 5
输出：
8
说明：正常的数字序列为8 9 10 11 12，最小为8

解题代码

 
class Solution:
    def __init__(self, string):
        self.string = string  # 字符串
 
    def getminint(self, k):
        map1 = {}
        for c in self.string:
            if c not in map1:
                map1[c]=0
            map1[c] += 1
 
        map2 = {}
        for i in range(1, k + 1):
            for c in str(i):
                if c not in map2:
                    map2[c]=0
                map2[c] += 1
                
        flag = True
        for c in map1:
            if map2.get(c) is None or map2[c] != map1[c]:
                flag=False
        if flag:
            return 1
 
        #注意题目到底写的是1000还是10000
        for i in range(2, 10000 - k + 2):
            for c in str(i - 1):
                map2[c] = map2.get(c, 0) -1
            for c in str(i + k - 1):
                map2[c] = map2.get(c, 0) +1
            flag = True
            for c in map1:
                if map2.get(c) is None or map2[c] != map1[c]:
                    flag=False
            if flag:
                return i
        return -1
        
s, cnt = map(str, input().split())
solution = Solution(s) 
print(solution.getminint(int(cnt)))