Given a string S of size N and a positive integer K, the task is to perform atmost K operations on string S to make it lexicographically smallest possible. In one operation, swap S[i] and S[j] and then change S[i] to any character, given 1 ? i < j ? N.
Examples:
Input: S = “geek”, K = 5
Output: aaaa
Explanation:
In 1st operation: take i = 1 and j = 4, swap S[1] and S[4] and then change S[1] to ‘a’. Modified string = “aeeg”.
In 2nd operation: take i = 2 and j=4, swap S[2] and S[4] and then change S[2] to ‘a’. Modified string = “aaee”.
In 3rd operation: take i = 3 and j = 4, swap S[3] and S[4] and then change S[3] to ‘a’. Modified string = “aaae”.
In 4th operation: take i = 3 and j = 4, swap S[3] and S[4] and then change S[3] to ‘a’. Modified string = “aaaa”.Input: S = “neveropen”, K = 6
Output: aaaaaaeeneveropen
Explanation: After 6 operations, lexicographically smallest string will be “aaaaaaeeneveropen”.
Approach: For K?N, the lexicographically smallest possible string will be ‘a’ repeated N times, since, in N operations, all the characters of S can be changed to ‘a’. For all other cases, the idea is to iterate the string S using variable i, find a suitable j for which S[j]>S[i], and then convert S[j] to S[i] and S[i] to ‘a’. Continue this process while K>0.
Follow the steps below to solve the problem:
- If K ? N, convert every character of string S to ‘a’ and print the string, S.
- Otherwise:
- Iterate in range[0, N-1] using variable i
- If K=0, break out of the loop.
- Iterate in range[i+1, N-1] using variable j
- If S[j]>S[i], set S[j]=S[i] and break out of the loop.
- If no such element found, i.e., j=N set S[j-1]=S[i].
- Set S[i]=’a’ and decrement K by 1.
- Print the string, S.
- Iterate in range[0, N-1] using variable i
Below is the implementation of the above approach:
C++
// C++ program to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the lexicographically// smallest possible string by performing// K operations on string Svoid smallestlexicographicstring(string s, int k){ // Store the size of string, s int n = s.size(); // Check if k>=n, if true, convert // every character to 'a' if (k >= n) { for (int i = 0; i < n; i++) { s[i] = 'a'; } cout << s; return; } // Iterate in range[0, n - 1] using i for (int i = 0; i < n; i++) { // When k reaches 0, break the loop if (k == 0) { break; } // If current character is 'a', // continue if (s[i] == 'a') continue; // Otherwise, iterate in the // range [i + 1, n - 1] using j for (int j = i + 1; j < n; j++) { // Check if s[j] > s[i] if (s[j] > s[i]) { // If true, set s[j] = s[i] // and break out of the loop s[j] = s[i]; break; } // Check if j reaches the last index else if (j == n - 1) s[j] = s[i]; } // Update S[i] s[i] = 'a'; // Decrement k by 1 k--; } // Print string cout << s;}// Driver Codeint main(){ // Given String, s string s = "neveropen"; // Given k int k = 6; // Function Call smallestlexicographicstring(s, k); return 0;} |
Java
// Java program to implement the above approach public class GFG{ // Function to find the lexicographically // smallest possible string by performing // K operations on string S static void smallestlexicographicstring(char[] s, int k) { // Store the size of string, s int n = s.length; // Check if k>=n, if true, convert // every character to 'a' if (k >= n) { for (int i = 0; i < n; i++) { s[i] = 'a'; } System.out.print(s); return; } // Iterate in range[0, n - 1] using i for (int i = 0; i < n; i++) { // When k reaches 0, break the loop if (k == 0) { break; } // If current character is 'a', // continue if (s[i] == 'a') continue; // Otherwise, iterate in the // range [i + 1, n - 1] using j for (int j = i + 1; j < n; j++) { // Check if s[j] > s[i] if (s[j] > s[i]) { // If true, set s[j] = s[i] // and break out of the loop s[j] = s[i]; break; } // Check if j reaches the last index else if (j == n - 1) s[j] = s[i]; } // Update S[i] s[i] = 'a'; // Decrement k by 1 k--; } // Print string System.out.print(s); } // Driver code public static void main(String[] args) { // Given String, s char[] s = ("neveropen").toCharArray(); // Given k int k = 6; // Function Call smallestlexicographicstring(s, k); }}// This code is contributed by divyesh072019. |
Python3
# Python3 program to implement the above approach# Function to find the lexicographically# smallest possible string by performing# K operations on string Sdef smallestlexicographicstring(s, k): # Store the size of string, s n = len(s) # Check if k>=n, if true, convert # every character to 'a' if (k >= n): for i in range(n): s[i] = 'a'; print(s, end = '') return; # Iterate in range[0, n - 1] using i for i in range(n): # When k reaches 0, break the loop if (k == 0): break; # If current character is 'a', # continue if (s[i] == 'a'): continue; # Otherwise, iterate in the # range [i + 1, n - 1] using j for j in range(i + 1, n): # Check if s[j] > s[i] if (s[j] > s[i]): # If true, set s[j] = s[i] # and break out of the loop s[j] = s[i]; break; # Check if j reaches the last index elif (j == n - 1): s[j] = s[i]; # Update S[i] s[i] = 'a'; # Decrement k by 1 k -= 1 # Print string print(''.join(s), end = '');# Driver Codeif __name__=='__main__': # Given String, s s = list("neveropen"); # Given k k = 6; # Function Call smallestlexicographicstring(s, k); # This code is contributed by rutvik_56. |
C#
// C# program to implement the above approach using System;using System.Collections.Generic;class GFG { // Function to find the lexicographically // smallest possible string by performing // K operations on string S static void smallestlexicographicstring(char[] s, int k) { // Store the size of string, s int n = s.Length; // Check if k>=n, if true, convert // every character to 'a' if (k >= n) { for (int i = 0; i < n; i++) { s[i] = 'a'; } Console.Write(s); return; } // Iterate in range[0, n - 1] using i for (int i = 0; i < n; i++) { // When k reaches 0, break the loop if (k == 0) { break; } // If current character is 'a', // continue if (s[i] == 'a') continue; // Otherwise, iterate in the // range [i + 1, n - 1] using j for (int j = i + 1; j < n; j++) { // Check if s[j] > s[i] if (s[j] > s[i]) { // If true, set s[j] = s[i] // and break out of the loop s[j] = s[i]; break; } // Check if j reaches the last index else if (j == n - 1) s[j] = s[i]; } // Update S[i] s[i] = 'a'; // Decrement k by 1 k--; } // Print string Console.Write(s); } // Driver code static void Main() { // Given String, s char[] s = ("neveropen").ToCharArray(); // Given k int k = 6; // Function Call smallestlexicographicstring(s, k); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the lexicographically // smallest possible string by performing // K operations on string S function smallestlexicographicstring(s, k) { // Store the size of string, s let n = s.length; // Check if k>=n, if true, convert // every character to 'a' if (k >= n) { for (let i = 0; i < n; i++) { s[i] = 'a'; } document.write(s); return; } // Iterate in range[0, n - 1] using i for (let i = 0; i < n; i++) { // When k reaches 0, break the loop if (k == 0) { break; } // If current character is 'a', // continue if (s[i] == 'a') continue; // Otherwise, iterate in the // range [i + 1, n - 1] using j for (let j = i + 1; j < n; j++) { // Check if s[j] > s[i] if (s[j].charCodeAt() > s[i].charCodeAt()) { // If true, set s[j] = s[i] // and break out of the loop s[j] = s[i]; break; } // Check if j reaches the last index else if (j == n - 1) s[j] = s[i]; } // Update S[i] s[i] = 'a'; // Decrement k by 1 k--; } // Print string document.write(s.join("")); } // Given String, s let s = ("neveropen").split(''); // Given k let k = 6; // Function Call smallestlexicographicstring(s, k);</script> |
Output:
aaaaaaeeneveropen
Time complexity: O(N2)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
