Lexicographically smallest string by repeatedly shifting one among first Ok characters to finish

Given a string str and a constructive integer Ok. In an operation, you’ll be able to choose a personality from the primary Ok characters and transfer it to the top, the duty is to search out the smallest lexicographic string that may be produced from string str after doing all of the required variety of operations.

Examples:

Enter: str = “dcab”, Ok = 2
Output: abdc
Rationalization: Take away ‘d’ from “dc” to get string as “cabd”, and take away ‘c’ from “ca” to get string as “abdc”.

Enter: str = “aaa”, Ok = 3
Output: aaa
Rationalization: Eradicating any character from the string wouldn’t make any distinction so unique string is the optimum reply.

Enter: str = “geeksforgeeks”, Ok = 0
Output: geeksforgeeks
Rationalization: No character might be chosen from an empty vary so the unique string is the optimum reply,

Strategy: To resolve the issue observe the beneath thought:

The concept to be carried out is to search out the smallest lexicographical string by eradicating the largest character from the primary Ok characters in every operation.

Observe the steps of the method:

• Initialize a map current to retailer the already encountered strings
• Whereas the present string shouldn’t be already encountered:
  • Discover the utmost character within the first Ok characters of the string.
  • Retailer the present string within the map current
  • Take away the utmost character discovered from its place and append it to the top of the string
• Return the primary string encountered within the map current.

The above method ensures that the string is not going to repeat and can carry on lowering to smaller lexicographical strings till the smallest one is reached.

Beneath is the implementation for the above method:

// C++ code for the above method:
#embody <bits/stdc++.h>
utilizing namespace std;

string smallestLexString(string str, int& okay)
{
    map<string, bool> current;
    char bigCh;
    int maxIndex;

    if (okay <= 0)
        return str;
    else if (okay >= str.size()) {
        kind(str.start(), str.finish());
        return str;
    }

    whereas (!current[str]) {
        bigCh="A";

        for (int i = 0; i < okay; i++) {
            if (bigCh < str[i]) {
                maxIndex = i;
                bigCh = str[i];
            }
        }

        current[str] = 1;
        str = str.substr(0, maxIndex)
              + str.substr(maxIndex + 1,
                           str.size() - maxIndex - 1)
              + str[maxIndex];
    }

    return current.start()->first;
}

// Driver's code
int predominant()
{
    string str = "geeksforgeeks";
    int Ok = 2;

    // Operate Name
    cout << smallestLexString(str, Ok);
    return 0;
}

Time Complexity: O(r*Ok)
Auxiliary Area: O(r), the place r is the variety of rotations till the string will get repeated and Ok is the vary of choice ranging from index 0.