Jobs

Interviews

Discussions

Orderly Queue

Hard

Asked by:

23 views

Topics:

StringsGreedy Algorithms

You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string.

Return the lexicographically smallest string you could have after applying the mentioned step any number of moves.

Example 1:

Input: s = "cba", k = 1
Output: "acb"
Explanation: 
In the first move, we move the 1^st character 'c' to the end, obtaining the string "bac".
In the second move, we move the 1^st character 'b' to the end, obtaining the final result "acb".

Example 2:

Input: s = "baaca", k = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1^st character 'b' to the end, obtaining the string "aacab".
In the second move, we move the 3^rd character 'c' to the end, obtaining the final result "aaabc".

Constraints:

1 <= k <= s.length <= 1000
s consist of lowercase English letters.

Try coding it in LeetCode

Orderly Queue

Hard

Asked by:

23 views

Topics:

StringsGreedy Algorithms

You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string.

Return the lexicographically smallest string you could have after applying the mentioned step any number of moves.

Example 1:

Input: s = "cba", k = 1
Output: "acb"
Explanation: 
In the first move, we move the 1^st character 'c' to the end, obtaining the string "bac".
In the second move, we move the 1^st character 'b' to the end, obtaining the final result "acb".

Example 2:

Input: s = "baaca", k = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1^st character 'b' to the end, obtaining the string "aacab".
In the second move, we move the 3^rd character 'c' to the end, obtaining the final result "aaabc".

Constraints:

1 <= k <= s.length <= 1000
s consist of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the string `s` and the value of `k`?
Can the input string `s` be empty or null?
Are there any special characters or encoding considerations for the input string `s` (e.g., ASCII, Unicode)?
If k is greater than the length of `s`, how should the operation behave?
If multiple lexicographically smallest strings can be obtained, is any one acceptable?

Brute Force Solution

Approach

The brute force approach to this problem involves exploring every possible reordering of the input string. We essentially try every shift possible and pick the lexicographically smallest one. This guarantees we find the absolute best arrangement.

Here's how the algorithm would work step-by-step:

Start with the original string.
Imagine picking the first character and moving it to the very end of the string.
Write down the new string you get from this move.
Repeat this process, each time taking the first character of the current string and placing it at the end, creating a new string.
Keep doing this until you've moved every character to the end, effectively trying all possible rotations of the original string.
Now that you have this collection of strings, compare them all, character by character, to find the one that would come earliest in a dictionary.
The string that comes first alphabetically is your answer.

Code Implementation

def orderly_queue_brute_force(input_string, queue_length):
    # If k > 1, we can always sort the string
    if queue_length > 1:
        return ''.join(sorted(input_string))

    smallest_string = input_string

    # Try every possible rotation of the string
    for shift_amount in range(len(input_string)):
        rotated_string = input_string[shift_amount:] + input_string[:shift_amount]

        # Compare the current rotation with the smallest one found so far
        if rotated_string < smallest_string:
            smallest_string = rotated_string

    return smallest_string

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates 'n' times, each time rotating the string, which takes O(n) time. Inside the main loop, comparing each generated string of length 'n' to find the lexicographically smallest string requires another O(n) operation per iteration. Therefore, the total runtime is proportional to n * n, resulting in a time complexity of O(n^2).

Space Complexity

O(N) – The provided solution generates all possible rotations of the input string of length N. Each rotation is a new string also of length N. These rotations are implicitly stored (even if not all at once in memory, the algorithm's logic implies their existence for comparison), requiring space proportional to N. Therefore, auxiliary space complexity is O(N) because it scales linearly with the size of the input string. No other significant data structures contribute to the overall space usage.

Optimal Solution

Approach

The problem asks to find the lexicographically smallest string you can make by repeatedly moving a character from the beginning to the end. The key insight is that if you can move more than one character at a time, you can simply sort the string to get the answer.

Here's how the algorithm would work step-by-step:

Check the number of characters you can move at once.
If you can move more than one, simply sort all characters and return the sorted string.
If you can only move one character, try every possible move. To do this, keep track of the smallest arrangement you've found so far.
For each move, shift the first character to the end of the string.
After each move, compare the new string with the smallest one you have. If it's smaller, replace the smallest one.
Once you've tried every move, the smallest arrangement you've kept track of is your final answer.

Code Implementation

def orderly_queue(input_string, k_moves):
    string_length = len(input_string)

    # If k > 1, we can sort
    if k_moves > 1:
        sorted_string = ''.join(sorted(input_string))
        return sorted_string

    #If only one move allowed, find the smallest string by rotations.
    smallest_string = input_string

    for i in range(string_length):
        rotated_string = input_string[1:] + input_string[:1]

        #Update smallest_string if we find a lexicographically smaller arrangement
        if rotated_string < smallest_string:
            smallest_string = rotated_string
        input_string = rotated_string

    return smallest_string

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm's time complexity depends on the value of k. If k > 1, the string is sorted, which takes O(n log n) time. However, if k = 1, we iterate through all n possible rotations of the string. In each iteration, a string comparison is performed, which takes O(n) time. Because string comparison occurs inside the loop (n iterations), the overall time complexity is O(n * n) in the worst-case when k = 1 and O(n log n) when k > 1. Therefore, the dominant term is O(n^2).

Space Complexity

O(N) – If k > 1, the algorithm sorts the string which may involve creating a new sorted string of length N, where N is the length of the input string. If k = 1, the algorithm keeps track of the smallest string found so far, also requiring space of size N. Therefore, the auxiliary space is dominated by storing a copy of the string, leading to O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input string	Return an empty string since there's nothing to process.
k = 1	Rotate the string all possible ways and compare lexicographically.
k > 1	The string can be sorted to get the lexicographically smallest string.
String with one character	Return the same string since no operation changes it.
String with duplicate characters	The algorithm will still perform the rotations or sorting to find the lexicographically smallest, regardless of duplicates.
Large string size (performance)	For k > 1, sorting the string is O(n log n), which is more efficient than rotating for very large strings, while k=1 iterates n times through n chars, being O(n^2).
String with all same characters	For k = 1, the algorithm will still rotate the string and compare, and for k > 1, sorting will result in the same string.
Null input string	Throw an IllegalArgumentException or return null to indicate an invalid input.

Empty input string

How to Handle:

Return an empty string since there's nothing to process.

k = 1

How to Handle:

Rotate the string all possible ways and compare lexicographically.

k > 1

How to Handle:

The string can be sorted to get the lexicographically smallest string.

String with one character

How to Handle:

Return the same string since no operation changes it.

String with duplicate characters

How to Handle:

The algorithm will still perform the rotations or sorting to find the lexicographically smallest, regardless of duplicates.

Large string size (performance)

How to Handle:

For k > 1, sorting the string is O(n log n), which is more efficient than rotating for very large strings, while k=1 iterates n times through n chars, being O(n^2).

String with all same characters

How to Handle:

For k = 1, the algorithm will still rotate the string and compare, and for k > 1, sorting will result in the same string.

Null input string

How to Handle:

Throw an IllegalArgumentException or return null to indicate an invalid input.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the string `s` and the value of `k`?
Can the input string `s` be empty or null?
Are there any special characters or encoding considerations for the input string `s` (e.g., ASCII, Unicode)?
If k is greater than the length of `s`, how should the operation behave?
If multiple lexicographically smallest strings can be obtained, is any one acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the original string.
Imagine picking the first character and moving it to the very end of the string.
Write down the new string you get from this move.
Repeat this process, each time taking the first character of the current string and placing it at the end, creating a new string.
Keep doing this until you've moved every character to the end, effectively trying all possible rotations of the original string.
Now that you have this collection of strings, compare them all, character by character, to find the one that would come earliest in a dictionary.
The string that comes first alphabetically is your answer.

Code Implementation

def orderly_queue_brute_force(input_string, queue_length):
    # If k > 1, we can always sort the string
    if queue_length > 1:
        return ''.join(sorted(input_string))

    smallest_string = input_string

    # Try every possible rotation of the string
    for shift_amount in range(len(input_string)):
        rotated_string = input_string[shift_amount:] + input_string[:shift_amount]

        # Compare the current rotation with the smallest one found so far
        if rotated_string < smallest_string:
            smallest_string = rotated_string

    return smallest_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Check the number of characters you can move at once.
If you can move more than one, simply sort all characters and return the sorted string.
If you can only move one character, try every possible move. To do this, keep track of the smallest arrangement you've found so far.
For each move, shift the first character to the end of the string.
After each move, compare the new string with the smallest one you have. If it's smaller, replace the smallest one.
Once you've tried every move, the smallest arrangement you've kept track of is your final answer.

Code Implementation

def orderly_queue(input_string, k_moves):
    string_length = len(input_string)

    # If k > 1, we can sort
    if k_moves > 1:
        sorted_string = ''.join(sorted(input_string))
        return sorted_string

    #If only one move allowed, find the smallest string by rotations.
    smallest_string = input_string

    for i in range(string_length):
        rotated_string = input_string[1:] + input_string[:1]

        #Update smallest_string if we find a lexicographically smaller arrangement
        if rotated_string < smallest_string:
            smallest_string = rotated_string
        input_string = rotated_string

    return smallest_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return an empty string since there's nothing to process.
k = 1	Rotate the string all possible ways and compare lexicographically.
k > 1	The string can be sorted to get the lexicographically smallest string.
String with one character	Return the same string since no operation changes it.
String with duplicate characters	The algorithm will still perform the rotations or sorting to find the lexicographically smallest, regardless of duplicates.
Large string size (performance)	For k > 1, sorting the string is O(n log n), which is more efficient than rotating for very large strings, while k=1 iterates n times through n chars, being O(n^2).
String with all same characters	For k = 1, the algorithm will still rotate the string and compare, and for k > 1, sorting will result in the same string.
Null input string	Throw an IllegalArgumentException or return null to indicate an invalid input.

Empty input string

How to Handle:

Return an empty string since there's nothing to process.

k = 1

How to Handle:

Rotate the string all possible ways and compare lexicographically.

k > 1

How to Handle:

The string can be sorted to get the lexicographically smallest string.

String with one character

How to Handle:

Return the same string since no operation changes it.

String with duplicate characters

How to Handle:

The algorithm will still perform the rotations or sorting to find the lexicographically smallest, regardless of duplicates.

Large string size (performance)

How to Handle:

For k > 1, sorting the string is O(n log n), which is more efficient than rotating for very large strings, while k=1 iterates n times through n chars, being O(n^2).

String with all same characters

How to Handle:

For k = 1, the algorithm will still rotate the string and compare, and for k > 1, sorting will result in the same string.

Null input string

How to Handle:

Throw an IllegalArgumentException or return null to indicate an invalid input.