Smallest Subsequence of Length K
Python
Hard
4 views
Problem Description
A string s and integer k are provided. Pick a subsequence of length k (keep order) with smallest lexicographic value. Output that subsequence.
Input Format
Line1: s. Line2: k.
Output Format
One line subsequence.
Official Solution
import sys
lines=sys.stdin.read().splitlines()
if len(lines)<2: sys.exit(0)
s=lines[0].strip()
k=int(lines[1].strip())
if k<=0:
sys.stdout.write('')
sys.exit(0)
if k>=len(s):
sys.stdout.write(s)
sys.exit(0)
stack=[]
remove=len(s)-k
for ch in s:
while remove>0 and stack and stack[-1]>ch:
stack.pop()
remove-=1
stack.append(ch)
res=''.join(stack[:k])
sys.stdout.write(res)
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!