Given a string str and a positive integer K. In an operation, you can select a character from the first K characters and move it to the end, the task is to find the smallest lexicographic string that can be made from string str after doing all the required number of operations.
Examples:
Input: str = “dcab”, K = 2
Output: abdc
Explanation: Remove ‘d’ from “dc” to get string as “cabd”, and remove ‘c’ from “ca” to get string as “abdc”.Input: str = “aaa”, K = 3
Output: aaa
Explanation: Removing any character from the string would not make any difference so original string is the optimal answer.Input: str = “neveropen”, K = 0
Output: neveropen
Explanation: No character can be selected from an empty range so the original string is the optimal answer,
Approach: To solve the problem follow the below idea:
The idea to be implemented is to find the smallest lexicographical string by removing the biggest character from the first K characters in each operation.
Follow the steps of the approach:
- Initialize a map present to store the already encountered strings
- While the current string is not already encountered:
- Find the maximum character in the first K characters of the string.
- Store the current string in the map present
- Remove the maximum character found from its position and append it to the end of the string
- Return the first string encountered in the map present.
The above approach ensures that the string will not repeat and will keep on reducing to smaller lexicographical strings until the smallest one is reached.
Below is the implementation for the above approach:
C++14
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;string smallestLexString(string str, int& k){ map<string, bool> present; char bigCh; int maxIndex; if (k <= 0) return str; else if (k >= str.length()) { sort(str.begin(), str.end()); return str; } while (!present[str]) { bigCh = 'A'; for (int i = 0; i < k; i++) { if (bigCh < str[i]) { maxIndex = i; bigCh = str[i]; } } present[str] = 1; str = str.substr(0, maxIndex) + str.substr(maxIndex + 1, str.length() - maxIndex - 1) + str[maxIndex]; } return present.begin()->first;}// Driver's codeint main(){ string str = "neveropen"; int K = 2; // Function Call cout << smallestLexString(str, K); return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG { public static String smallestLexString(String str, int k) { Map<String, Boolean> present = new HashMap<>(); char bigCh; int maxIndex = 0; if (k <= 0) { return str; } else if (k >= str.length()) { char[] strChars = str.toCharArray(); Arrays.sort(strChars); return new String(strChars); } while (!present.containsKey(str)) { bigCh = 'A'; for (int i = 0; i < k; i++) { if (bigCh < str.charAt(i)) { maxIndex = i; bigCh = str.charAt(i); } } present.put(str, true); str = str.substring(0, maxIndex) + str.substring(maxIndex + 1, str.length()) + bigCh; } String[] keys = new String[present.keySet().size()]; present.keySet().toArray(keys); Arrays.sort(keys); return keys[0]; } // Driver's code public static void main(String[] args) { String str = "neveropen"; int k = 2; // Function call System.out.println(smallestLexString(str, k)); }}// This code is contributed by prasad264 |
Python3
# Python code for the above approach:def smallestLexString(string, k): present = {} bigCh = '' max_index = 0 if k <= 0: return string elif k >= len(string): string_chars = list(string) string_chars.sort() return ''.join(string_chars) while string not in present: bigCh = 'A' for i in range(k): if bigCh < string[i]: max_index = i bigCh = string[i] present[string] = True string = string[:max_index] + string[max_index+1:] + bigCh keys = list(present.keys()) keys.sort() return keys[0]# Driver's codestring = "neveropen"k = 2# Function callprint(smallestLexString(string, k))# This code is contributed by prasad264 |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class MainClass { public static string smallestLexString(string str, int k) { Dictionary<string, bool> present = new Dictionary<string, bool>(); char bigCh; int maxIndex = 0; if (k <= 0) return str; else if (k >= str.Length) { char[] strChars = str.ToCharArray(); Array.Sort(strChars); return new string(strChars); } while (!present.ContainsKey(str)) { bigCh = 'A'; for (int i = 0; i < k; i++) { if (bigCh < str[i]) { maxIndex = i; bigCh = str[i]; } } present[str] = true; str = str.Substring(0, maxIndex) + str.Substring(maxIndex + 1, str.Length - maxIndex - 1) + bigCh; } string[] keys = new string[present.Keys.Count]; present.Keys.CopyTo(keys, 0); Array.Sort(keys); return keys[0]; } // Driver code public static void Main(string[] args) { string str = "neveropen"; int k = 2; // Function call Console.WriteLine(smallestLexString(str, k)); }}// This code is contributed by lokeshpotta20. |
Javascript
// JavaScript code for the above approach:function smallestLexString(str, k) { let present = new Map(); let bigCh; let maxIndex = 0; if (k <= 0) { return str; } else if (k >= str.length) { let strChars = str.split(''); strChars.sort(); return strChars.join(''); } while (!present.has(str)) { bigCh = 'A'; for (let i = 0; i < k; i++) { if (bigCh < str.charAt(i)) { maxIndex = i; bigCh = str.charAt(i); } } present.set(str, true); str = str.substring(0, maxIndex) + str.substring(maxIndex + 1, str.length) + bigCh; } let keys = [...present.keys()]; keys.sort(); return keys[0];}// Driver's codelet str = "neveropen";let k = 2;// Function callconsole.log(smallestLexString(str, k));// This code is contributed by prasad264 |
eeeksgeksforg
Time Complexity: O(r*K)
Auxiliary Space: O(r), where r is the number of rotations until the string gets repeated and K is the range of selection starting from index 0.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
