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:
- Iterar en el rango [0, N-1] usando la variable i
- Si K=0 , sal del bucle .
- Iterar en el rango [i+1, N-1] usando la variable j
- Si S[j]>S[i] , establece S[j]=S[i] y sal del bucle .
- Si no se encuentra tal elemento, es decir, j=N establece S[j-1]=S[i] .
- Establezca S[i]=’a’ y disminuya K en 1.
- Imprime la string, S .
- Iterar en el rango [0, N-1] usando la variable i
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>
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