Dada una string S y un entero K , la tarea es encontrar la string lexicográficamente más pequeña posible después de invertir cualquier substring de cualquier longitud exactamente K veces.
Ejemplos:
Entrada : S = “fgazcbdfge”, K = 3
Salida : abcdgfzfge
Explicación : Después de la primera operación: S = “agfzcbdfge”, en S seleccione S[0 – 2] = “fga” e inviértalo
Después de la segunda operación: S = “abczfgdfge ”, en S seleccione S[2 – 4] = “fzc” e inviértalo
Después de la 3ª operación: S = “abcdgfzfge”, en S seleccione S[3 – 6] = “zfgd” e inviértalo.Entrada : S = “abcdefg”, K = 5
Salida : abcdefg
Explicación : La string ya es lexicográficamente mínima posible.
Por lo tanto, elija 5 substrings que tengan una longitud de 1. Por lo tanto, la string permanecerá sin cambios.
Enfoque : Para formar la string lexicográficamente más pequeña en K pasos, en cada paso seleccione un número entero L donde S[L] es el carácter antes del cual todos los caracteres están ordenados y un número entero R donde S[R] es el carácter que tiene que colocarse en S[L+1] para que todos los caracteres hasta S[L+1] estén ordenados. Invierta la substring S[L..R] en cada paso y, finalmente, se obtendrá la string requerida. Siga los pasos a continuación para resolver el problema:
- Deje que la string dada sea S , cree otra string S1 igual a S y luego ordene S1 en orden creciente.
- Este algoritmo requiere tres bucles anidados, el bucle exterior se ejecutará de 0 a K (número de operaciones)
- En cada operación, busque dos enteros L y R , después de haberlos encontrado, invertimos la substring S[L … R] y continuamos igual para las operaciones posteriores.
- Usando dos bucles anidados, busque caracteres de S1 en S según la cantidad de operaciones.
- Dado que solo es necesario invertir una substring en una operación, solo busque un carácter de S1 en S que sea S[R] (el carácter que debe colocarse después de los caracteres de S ya ordenados en operaciones anteriores) y también busque S [L] (la substring S[0…L-1] está ordenada para que no tengamos que hacer nada con ella, S[R] se colocará en S[L+1] ).
- Después de K operaciones, se obtiene la string lexicográficamente más pequeña posible.
Ilustración:
En la ilustración anterior, dado que los primeros tres caracteres de la string original estaban ordenados, no tenemos que involucrarlos en ninguna operación Busque el carácter que aparecerá después de ellos en el orden ordenado, suponga que aparece en el índice R (el carácter sea S[R]) seleccionamos el índice del carácter después de los primeros tres caracteres como R (el carácter será S[R]) Ahora invertimos la substring S[L…R] que dará como resultado el carácter S[R] para aparecer en S[L+1] y ahora los primeros 4 caracteres de la string S están ordenados
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the lexicographically
// minimum string after k operations
string findStr(string s, int k)
{
// Sorted string
string ss = s;
sort(ss.begin(), ss.end());
// String after each operation
string ans = "";
for (int i = 0; i < k; i++) {
ans = "";
int r = 0;
int l = -1;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < ss.length(); j++) {
if (s[j] == ss[i] && i == j) {
l = i;
break;
}
else if (s[j] == ss[i]) {
r = j;
break;
}
}
if (r > 0)
// to avoid unnecessary checking
break;
}
// There is no group of sorted characters
// in the beginning of the string S
if (l == -1) {
for (int i = r; i >= 0; i--)
ans.push_back(s[i]);
for (int i = r + 1; i < s.length(); i++)
ans.push_back(s[i]);
}
// string S is already sorted or S = SS
else if (l == s.length() - 1) {
ans = s;
}
// Some part of string S in the beginning
// is sorted
else {
for (int i = 0; i <= l; i++)
ans.push_back(s[i]);
for (int i = r; i > l; i--)
ans.push_back(s[i]);
for (int i = r + 1; i < s.length(); i++)
ans.push_back(s[i]);
}
// cout << "after " << i+1 << " operations
// : " << ans << '\n'; use the above line of
// code to see how S changes after every
// operation
s = ans;
}
return s;
}
// Driver Code
int main()
{
// Number of operations
int K = 3;
// Given string
string S = "fgazcbdfge";
// Final answer string
string ans = findStr(S, K);
cout << ans;
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG {
// Function to return the lexicographically
// minimum string after k operations
static String findStr(String s, int k)
{
// Sorted string
String ss = s;
char[] arr = ss.toCharArray();
Arrays.sort(arr);
ss = new String(arr);
// String after each operation
String ans = "";
for (int a = 0; a < k; a++) {
ans = "";
int r = 0;
int l = -1;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < ss.length(); j++) {
if (s.charAt(j) == ss.charAt(i)
&& i == j) {
l = i;
break;
}
else if (s.charAt(j) == ss.charAt(i)) {
r = j;
break;
}
}
if (r > 0)
// to avoid unnecessary checking
break;
}
// There is no group of sorted characters
// in the beginning of the string S
if (l == -1) {
for (int i = r; i >= 0; i--)
ans += s.charAt(i);
for (int i = r + 1; i < s.length(); i++)
ans += s.charAt(i);
}
// string S is already sorted or S = SS
else if (l == s.length() - 1) {
ans = s;
}
// Some part of string S in the beginning
// is sorted
else {
for (int i = 0; i <= l; i++)
ans += s.charAt(i);
for (int i = r; i > l; i--)
ans += s.charAt(i);
for (int i = r + 1; i < s.length(); i++)
ans += s.charAt(i);
}
// cout << "after " << i+1 << " operations
// : " << ans << '\n'; use the above line of
// code to see how S changes after every
// operation
s = ans;
}
return s;
}
// Driver Code
public static void main(String[] args)
{
// Number of operations
int K = 3;
// Given string
String S = "fgazcbdfge";
// Final answer string
String ans = findStr(S, K);
System.out.print(ans);
}
}
// This code is contributed by ukasp.
Python3
# python3 code to implement the approach
# Function to return the lexicographically
# minimum string after k operations
def findStr(s, k):
# Sorted string
ss = list(s)
ss.sort()
# String after each operation
ans = ""
for i in range(0, k):
ans = ""
r = 0
l = -1
for i in range(0, len(s)):
for j in range(0, len(ss)):
if (s[j] == ss[i] and i == j):
l = i
break
elif (s[j] == ss[i]):
r = j
break
if (r > 0):
# to avoid unnecessary checking
break
# There is no group of sorted characters
# in the beginning of the string S
if (l == -1):
for i in range(r, -1, -1):
ans += s[i]
for i in range(r+1, len(s)):
ans += s[i]
# string S is already sorted or S = SS
elif (l == len(s) - 1):
ans = s
# Some part of string S in the beginning
# is sorted
else:
for i in range(0, l+1):
ans += s[i]
for i in range(r, l, -1):
ans += s[i]
for i in range(r + 1, len(s)):
ans += s[i]
# print(f"after {i+1} operations: {ans}")
# use the above line of
# code to see how S changes after every
# operation
s = ans
return s
# Driver Code
if __name__ == "__main__":
# Number of operations
K = 3
# Given string
S = "fgazcbdfge"
# Final answer string
ans = findStr(S, K)
print(ans)
# This code is contributed by rakeshsahni
C#
// C# code to implement the approach
using System;
class GFG {
// Function to return the lexicographically
// minimum string after k operations
static string findStr(string s, int k)
{
// Sorted string
string ss = s;
char[] arr = ss.ToCharArray();
Array.Sort(arr);
ss = new string(arr);
// String after each operation
string ans = "";
for (int a = 0; a < k; a++) {
ans = "";
int r = 0;
int l = -1;
for (int i = 0; i < s.Length; i++) {
for (int j = 0; j < ss.Length; j++) {
if (s[j] == ss[i] && i == j) {
l = i;
break;
}
else if (s[j] == ss[i]) {
r = j;
break;
}
}
if (r > 0)
// to avoid unnecessary checking
break;
}
// There is no group of sorted characters
// in the beginning of the string S
if (l == -1) {
for (int i = r; i >= 0; i--)
ans += s[i];
for (int i = r + 1; i < s.Length; i++)
ans += s[i];
}
// string S is already sorted or S = SS
else if (l == s.Length - 1) {
ans = s;
}
// Some part of string S in the beginning
// is sorted
else {
for (int i = 0; i <= l; i++)
ans += s[i];
for (int i = r; i > l; i--)
ans += s[i];
for (int i = r + 1; i < s.Length; i++)
ans += s[i];
}
// cout << "after " << i+1 << " operations
// : " << ans << '\n'; use the above line of
// code to see how S changes after every
// operation
s = ans;
}
return s;
}
// Driver Code
public static void Main()
{
// Number of operations
int K = 3;
// Given string
string S = "fgazcbdfge";
// Final answer string
string ans = findStr(S, K);
Console.Write(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to return the lexicographically
// minimum string after k operations
function findStr(s, k)
{
// Sorted string
let ss = s.split('');
ss.sort(function (a, b) { return a.charCodeAt(0) - b.charCodeAt(0) })
// String after each operation
let ans = [];
for (let i = 0; i < k; i++) {
ans = [];
let r = 0;
let l = -1;
for (let i = 0; i < s.length; i++)
{
for (let j = 0; j < ss.length; j++)
{
if (s[j] == ss[i] && i == j)
{
l = i;
break;
}
else if (s[j] == ss[i]) {
r = j;
break;
}
}
if (r > 0)
// to avoid unnecessary checking
break;
}
// There is no group of sorted characters
// in the beginning of the string S
if (l == -1) {
for (let i = r; i >= 0; i--)
ans.push(s[i]);
for (let i = r + 1; i < s.length; i++)
ans.push(s[i]);
}
// string S is already sorted or S = SS
else if (l == s.length - 1) {
ans = s;
}
// Some part of string S in the beginning
// is sorted
else {
for (let i = 0; i <= l; i++)
ans.push(s[i]);
for (let i = r; i > l; i--)
ans.push(s[i]);
for (let i = r + 1; i < s.length; i++)
ans.push(s[i]);
}
// code to see how S changes after every
// operation
s = [...ans];
}
return s.join('');
}
// Driver Code
// Number of operations
let K = 3;
// Given string
let S = "fgazcbdfge";
// Final answer string
let ans = findStr(S, K);
document.write(ans);
// This code is contributed by Potta Lokesh
</script>
abcdgfzfge
Complejidad de tiempo: O(K * N 2 ) donde N es la longitud de la string
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshverma28 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA