La string lexicográficamente más pequeña posible al realizar operaciones K en una string dada

Dada una string S de tamaño N y un entero positivo K , la tarea es realizar como máximo K operaciones en la string S para que sea lexicográficamente lo  más pequeña posible. En una operación, intercambie S[i] y S[j] y luego cambie S[i] a cualquier carácter, dado 1 ≤ i < j ≤ N .

Ejemplos:

Entrada: S = “geek”, K = 5
Salida: aaaa
Explicación: 
En la primera operación: tome i = 1 y j = 4, intercambie S[1] y S[4] y luego cambie S[1] a ‘a’ . String modificada = “aeeg”.
En la segunda operación: tome i = 2 y j=4, intercambie S[2] y S[4] y luego cambie S[2] a ‘a’. String modificada = “aaee”.
En la tercera operación: tome i = 3 y j = 4, intercambie S[3] y S[4] y luego cambie S[3] a ‘a’. String modificada = “aaae”.
En la cuarta operación: tome i = 3 y j = 4, intercambie S[3] y S[4] y luego cambie S[3] a ‘a’. String modificada = “aaaa”.

Entrada: S = “geeksforgeeks”, K = 6
Salida: aaaaaaeegeeks
Explicación: Después de 6 operaciones, lexicográficamente la string más pequeña será “aaaaaaeegeeks”.

Enfoque: Para K≥N , la string lexicográficamente más pequeña posible será ‘a’ repetida N veces, ya que, en N operaciones, todos los caracteres de S se pueden cambiar a ‘a’ . Para todos los demás casos, la idea es iterar la string S usando la variable i , encontrar un j adecuado para el cual S[j]>S[i] , y luego convertir S[j] a S[i] y S[i] a ‘a’ . Continúe este proceso mientras K>0 .

Siga los pasos a continuación para resolver el problema:

  • Si K ≥ N , convierta cada carácter de la string S en ‘a’ e imprima la string, S .
  • De lo contrario:

A continuación se muestra la implementación del enfoque anterior:

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 = "geeksforgeeks";
 
    // 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 = ("geeksforgeeks").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("geeksforgeeks");
 
    # 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 = ("geeksforgeeks").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 = ("geeksforgeeks").split('');
    
    // Given k
    let k = 6;
    
    // Function Call
    smallestlexicographicstring(s, k);
 
</script>
Producción: 

aaaaaaeegeeks

 

Complejidad temporal: O(N 2 )
Espacio auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por sourav2901 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *