Solution For Orderly Queue

Problem Description:
We have a string S of lowercase letters, and an integer array shifts.
We want to shift every occurrence of letter S[i], by shifts[i] positions.
After we do this, we have a new string where every occurrence of S[i] is shifted by shifts[i] positions.
We then want to take the final string and move the first letter of it to the end of the string,
repeating this operation K times in total.
Return the final string after such manipulation.

Solution:
This problem can be solved by iteratively applying the shifts and rotations in a single pass.
We keep track of the total shift applied so far and update it with the current shift as we scan each character from the end of the string to the beginning.
We perform the rotation of the first character after all the shifts have been applied.

Algorithm:
1. Initialize a variable “total_shift” to 0.
2. Iterate the shifts array from the end, and do the following
a. Update “total_shift” with the current shift value
b. Calculate the shift required for the current character using “total_shift” and the length of the alphabet (26).
c. Apply the shift to the current character using ASCII values to convert to and from integers. Store the shifted character in a buffer array.
3. Perform the rotation K times by moving the first character of the buffer array to the end.
4. Concatenate the buffer array into a single string and return it as the final result.

Time Complexity:
The solution has a time complexity of O(n), where n is the length of the string S.

Space Complexity:
The solution has a space complexity of O(n), where n is the length of the string S, as we need to store the shifted characters in a buffer array.

Code:

class Solution {
public:
string shiftingLetters(string S, vector& shifts) {
int n = S.size();
vector buffer(n);
int total_shift = 0;

    for(int i=n-1; i>=0; i--) {
        total_shift = (total_shift + shifts[i]) % 26;
        int shift = (S[i] - 'a' + total_shift) % 26;
        buffer[i] = (shift + 'a');
    }

    for(int k=0; k<K; k++) {
        char temp = buffer[0];
        for(int i=1; i<n; i++) {
            buffer[i-1] = buffer[i];
        }
        buffer[n-1] = temp;
    }

    string result(buffer.begin(), buffer.end());
    return result;
}

};

Step by Step Implementation For Orderly Queue

class Solution {
    public String orderlyQueue(String S, int K) {
        // if K is greater than 1, we can always rearrange the string to be the
        // lexicographically smallest string
        if (K > 1) {
            char[] chars = S.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        }
        
        // if K is 1, we need to find the lexicographically smallest string that
        // can be obtained by rotating the given string
        String minString = S;
        for (int i = 1; i < S.length(); i++) {
            String rotatedString = S.substring(i) + S.substring(0, i);
            if (rotatedString.compareTo(minString) < 0) {
                minString = rotatedString;
            }
        }
        return minString;
    }
}

def orderlyQueue(S, K):
        # if K is greater than 1, we can always rotate the string to get the lexicographically smallest string
        if K > 1:
            return S[1:] + S[0]
        # if K is 1, we need to find the smallest string that can be generated by swapping 2 adjacent characters
        else:
            # initialize the minimum string to be the input string S
            min_str = S
            # iterate through the string S
            for i in range(len(S)):
                # if the current string is lexicographically smaller than the minimum string, update the minimum string
                if S[i:] + S[:i] < min_str:
                    min_str = S[i:] + S[:i]
            # return the minimum string
            return min_str

var orderlyQueue = function(S, K) {
    // if K is greater than 1, we can always rotate the string to get the smallest lexicographical order
    // so we only need to worry about K = 0 or 1
    if (K === 0) {
        // if K is 0, then we need to find the smallest lexicographical order of S
        // we can do this by sorting S
        return S.split('').sort().join('');
    } else {
        // if K is 1, then we need to find the smallest lexicographical order of S
        // we can do this by rotating S until the first character is the smallest character in S
        let minChar = 'z';
        // find the smallest character in S
        for (let i = 0; i < S.length; i++) {
            if (S[i] < minChar) {
                minChar = S[i];
            }
        }
        // now rotate S until the first character is the smallest character in S
        while (S[0] !== minChar) {
            S = S.slice(1) + S[0];
        }
        return S;
    }
};

There are two cases for this problem:

1) If k > 1, we can always swap the first element with the last element to get the smallest lexicographical order.

2) If k == 1, we need to find the smallest element from the array and swap it with the first element.

using System; 

public class Solution { 

//O(N) time and O(1) space 
public string OrderlyQueue(string S, int K) { 

if (K == 1) 

{ 

//if K is 1, the smallest string is the one that has the first character in alphabetical order 

//compare all substrings starting with the first character to find the smallest one 

string smallest = S; 

for (int i = 1; i < S.Length; i++) 

{ 

if (S[i] < S[0]) 

{ 

smallest = S.Substring(i) + S.Substring(0, i); 

} 

} 

return smallest; 

} 

else 

{ 

//if K is greater than 1, the smallest string is the string sorted in alphabetical order 

//this can be done in O(NlogN) time using an array sort 

char[] chars = S.ToCharArray(); 

Array.Sort(chars); 

return new string(chars); 

} 

} 

}