We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Orderly Queue

Number: 935

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given a string s and an integer k, you are allowed to pick one of the first k letters of s and append it to the end of the string. You can apply this move any number of times. The goal is to find and return the lexicographically smallest string possible after any sequence of moves.

Key Insights

  • If k equals 1, the only operation allowed is rotating the string. Therefore, the final string must be one of the rotations of s.
  • When k > 1, it is possible to rearrange the string arbitrarily. In this case, the lexicographically smallest string is simply the sorted version of s.
  • The key observation for k > 1 is that the move allows swaps of adjacent characters, which can be leveraged to achieve any permutation of s.

Space and Time Complexity

Time Complexity:

  • O(n²) when k == 1 because we generate n rotations and each comparison may take O(n) in the worst-case.
  • O(n log n) when k > 1 due to sorting the string.

Space Complexity:

  • O(n) to store the candidate rotations or the sorted string.

Solution

For k == 1, iterate over all rotations of the string s by splitting it at every possible index, then track the lexicographically smallest rotation. For k > 1, since any order can be achieved, sort the characters of s and return the sorted string. This approach employs simple string manipulation and comparison techniques. The key data structures involved are strings (or arrays of characters in some languages), and the algorithmic approach involves either simulation of rotations or sorting, based on the value of k.

Code Solutions

# Python implementation
def orderlyQueue(s: str, k: int) -> str:
    if k == 1:
        # Only rotations are possible
        best = s
        n = len(s)
        # Generate all possible rotations and track the smallest one
        for i in range(n):
            candidate = s[i:] + s[:i]
            if candidate < best:
                best = candidate
        return best
    else:
        # When k > 1, any permutation is possible so sort the characters
        return ''.join(sorted(s))

# Example usage
if __name__ == "__main__":
    s = "baaca"
    k = 3
    print(orderlyQueue(s, k))  # Expected output: "aaabc"
← Back to All Questions