Wednesday, May 31, 2023
HomeSoftware DevelopmentLexicographically smallest string by repeatedly transferring certainly one of first Ok characters...

# Lexicographically smallest string by repeatedly transferring certainly one of 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 tip, the duty is to seek out the smallest lexicographic string that may be comprised of 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 authentic string is the optimum reply.

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

Strategy: To resolve the issue observe the under thought:

The thought to be applied is to seek out the smallest lexicographical string by eradicating the largest character from the primary Ok characters in every operation.

Comply with the steps of the strategy:

• Initialize a map current to retailer the already encountered strings
• Whereas the present string will not 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 tip of the string
• Return the primary string encountered within the map current.

The above strategy ensures that the string won’t repeat and can carry on decreasing to smaller lexicographical strings till the smallest one is reached.

Beneath is the implementation for the above strategy:

## C++14

 `#embrace ` `utilizing` `namespace` `std;` ` `  `string smallestLexString(string str, ``int``& ok)` `{` `    ``map current;` `    ``char` `bigCh;` `    ``int` `maxIndex;` ` `  `    ``if` `(ok <= 0)` `        ``return` `str;` `    ``else` `if` `(ok >= str.size()) {` `        ``type(str.start(), str.finish());` `        ``return` `str;` `    ``}` ` `  `    ``whereas` `(!current[str]) {` `        ``bigCh = ``'A'``;` ` `  `        ``for` `(``int` `i = 0; i < ok; 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;` `}` ` `  `int` `fundamental()` `{` `    ``string str = ``"geeksforgeeks"``;` `    ``int` `Ok = 2;` ` `  `    ` `    ``cout << smallestLexString(str, Ok);` `    ``return` `0;` `}`

Time Complexity: O(r*Ok)
Auxiliary House: 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.

RELATED ARTICLES