Editorial for Mock CCC '21 S3 - Lexicographically Smallest Permutation Subsequence
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
For each character, maintain a frequency count of how many times it appears.
Sweep over the string from left to right, incrementally building the desired permutation. We maintain the invariant that the prefix of the permutation we have built thus far is the lexicographically smallest prefix that is valid. We can pop elements from the end if and only if they are larger than the current element we are considering and also appear later on.
Comments