Lexicographically smallest string possible by performing K operations on a given string

0 0 7 minutes read

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 = “zambiatek”, K = 6
Output: aaaaaaeezambiatek
Explanation: After 6 operations, lexicographically smallest string will be “aaaaaaeezambiatek”.

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.

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 S
void 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 Code
int main()
{
 
    // Given String, s
    string s = "zambiatek";
 
    // 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 = ("zambiatek").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 S
def 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 Code
if __name__=='__main__':
 
    # Given String, s
    s = list("zambiatek");
 
    # 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 = ("zambiatek").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 = ("zambiatek").split('');
    
    // Given k
    let k = 6;
    
    // Function Call
    smallestlexicographicstring(s, k);
 
</script>

Output:

aaaaaaeezambiatek

Time complexity: O(N²)
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 zambiatek!