FastPrep
Problem · String

Lexicographically Smallest Task Queue

Learn this problem
● MediumAGAgodaCONTRACTOA

Problem statement

A system manages a queue of tasks represented by a string taskQueue. Each character is one of:

  • '1': low priority
  • '2': medium priority
  • '3': high priority

You may perform adjacent swaps any number of times, but only for these unordered adjacent pairs:

  1. swap adjacent '1' and '2' tasks
  2. swap adjacent '2' and '3' tasks

You cannot directly swap adjacent '1' and '3' tasks. Therefore, after removing all '2' tasks from the string, the relative order of the remaining '1' and '3' tasks is invariant. Return the lexicographically smallest task order that can be obtained under these swap rules. Do not assume the answer is always the fully sorted string.

A task order a is lexicographically smaller than task order b if, at the first position where they differ, a has the smaller priority character.

Function

getSmallestTaskQueue(taskQueue: String) → String

Examples

Example 1

taskQueue = "13212"return = "12231"

The '2' tasks can move across both '1' and '3' tasks, but '1' and '3' cannot swap directly. The non-'2' subsequence in "13212" is "131", and that relative order must remain. The smallest reachable placement of the two '2' tasks gives "12231".

Constraints

  • 1 <= taskQueue.length <= 2 * 10^5
  • taskQueue contains only '1', '2', and '3'.

More Agoda problems

drafts saved locally
public String getSmallestTaskQueue(String taskQueue) {
  // write your code here
}
taskQueue"13212"
expected"12231"
checking account