python-programs/compressed_string.py at master · chinmayb/python-programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Given a compressed string in the format: a2b1ca; where given string means aabca
# Given Q test cases and corresponding k inputs
# find the kth alphabet in the sorted uncompressed string.
# If kth alphabet does not exist return -1

inp_str=raw_input()
len_str=len(inp_str)
hashed_str= {}
foriinxrange(len_str):
if92<=ord(inp_str[i]) <=117:
n=0
j=i
while (j+1<=len_str-1and92>ord(inp_str[j+1])):
n+=1
j+=1
temp=inp_str[i+1:j+1]
ifn==0:
temp=1
temp=int(temp)
ifinp_str[i] inhashed_str.keys():
hashed_str[inp_str[i]] +=int(temp)
else:
hashed_str[inp_str[i]] =int(temp)
i=j
sorted_hashed_str=sorted(hashed_str.items(), key=lambdax: x[0])
printsorted_hashed_str

sum_vals=0
foriinxrange(len(sorted_hashed_str)):
sum_vals+=sorted_hashed_str[i][1]
# print sum_vals

Q=input()
assert (1<=Q<=10**5)
for_inxrange(Q):
k=input()
assert (1<=k<=10**18)
x=0
i=0
ifk>sum_vals:
print-1
else:
whilex<k:
x+=sorted_hashed_str[i][1]
i+=1
printsorted_hashed_str[i-1][0]