Dada una string S de tamaño N , que tiene letras en minúsculas, la tarea es encontrar la string lexicográficamente mínima después de mover una subsecuencia al final de la string solo una vez.
Ejemplo:
Entrada: N = 3, S = “asa” Salida: aas Explicación: La subsecuencia óptima es “s” . Eliminado, y añadido por fin. Por lo tanto, la string final es ‘aa’ + ‘s’ = ‘aas’
Entrada: N = 7, S = “fabccac” Salida: aacfbcc Explicación: La subsecuencia óptima es “fbcc” . Cualquier otra subsecuencia no dará el mínimo Por lo tanto, la string final es ‘aac’ + ‘fbcc’ = ‘aacfbcc’
Planteamiento: El problema se puede resolver con base en la siguiente observación:
Para encontrar la string lexicográficamente mínima, la subsecuencia seleccionada debe seguir el patrón.
- El primer carácter de la subsecuencia seleccionada que se eliminará debe ser igual o mayor que el último carácter de la subsecuencia retenida.
- La subsecuencia no seleccionada formará una secuencia no decreciente.
Siga los pasos para resolver el problema:
- Inicialice una array booleana para mantener la posición de los caracteres si se incluyen en la subsecuencia para barajar o no.
- Mantenga una pila para encontrar una subsecuencia no decreciente de caracteres retenidos
- En cada carácter, saque todos los caracteres mayores que el carácter actual de la pila.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find lexicographically minimum
string LexMin(int n, string s)
{
// Boolean array for storing positions
// and frequencies
vector<int> last(26, -1);
for (int i = 0; i < n; i++) {
last[s[i] - 'a'] = i;
}
int dig = 0;
int mx = 26;
// ans for storing resultant string
// ans1 for leftout and ans2 for picked up
string ans = s, ans1, ans2;
for (int i = 0; i < n; i++) {
// For every i we will find its
// last occurrence last[dig]
while (dig < 26 && i > last[dig])
dig++;
if (dig == mx) {
string ans3 = ans2, ans4;
for (int j = i; j < n; j++) {
// Adding the character
if (s[j] == ('a' + mx)) {
ans4.push_back(s[j]);
}
else {
ans3.push_back(s[j]);
}
}
// Remove the other half and
// store the substring upto i
ans2 += s.substr(i);
// Find out the minimum
// and put it into ans
ans = min(ans, ans1
+ min(ans2, ans4 + ans3));
break;
}
else if (dig > mx) {
ans = min(ans, ans1
+ ans2 + s.substr(i));
break;
}
// ans1 holds value retaining values
if (s[i] == ('a' + dig)) {
ans1.push_back(s[i]);
}
else {
if (mx == 26)
mx = (s[i] - 'a');
ans2.push_back(s[i]);
}
// Corner cases
if (i == n - 1)
ans = min(ans, ans1 + ans2);
}
// Return the ans
return ans;
}
// Driver code
int main()
{
int N = 3;
string s = "asa";
// Function call
cout << LexMin(N, s) << endl;
return 0;
}
Python3
# Python3 code for the above approach
# Function to find lexicographically minimum
def LexMin(n, s) :
# Boolean array for storing positions
# and frequencies
last = [-1] * 26;
for i in range(n) :
last[ord(s[i]) - ord('a')] = i;
dig = 0;
mx = 26;
# ans for storing resultant string
# ans1 for leftout and ans2 for picked up
ans = s;
ans1,ans2 = "","";
for i in range(n) :
# For every i we will find its
# last occurrence last[dig]
while (dig < 26 and i > last[dig]) :
dig += 1;
if (dig == mx) :
ans3 = ans2;
ans4 = "";
for j in range(1, n) :
# Adding the character
if (ord(s[j]) == (ord('a') + mx)) :
ans4 += s[j] ;
else :
ans3 += s[j];
# Remove the other half and
# store the substring upto i
ans2 += s[:i];
# Find out the minimum
# and put it into ans
ans = min(ans, ans1 + min(ans2, ans4 + ans3));
break;
elif (dig > mx) :
ans = min(ans, ans1 + ans2 + s[:i]);
break;
# ans1 holds value retaining values
if (ord(s[i]) == (ord('a') + dig)) :
ans1 += s[i];
else :
if (mx == 26) :
mx = (ord(s[i]) - ord('a'));
ans2 += s[i];
# Corner cases
if (i == n - 1) :
ans = min(ans, ans1 + ans2);
# Return the ans
return ans;
# Driver code
if __name__ == "__main__" :
N = 3;
s = "asa";
# Function call
print(LexMin(N, s));
# This code is contributed by AnkThon
Javascript
<script>
// JavaScript code for the above approach
// Function to find lexicographically minimum
function LexMin(n,s)
{
// Boolean array for storing positions
// and frequencies
let last = new Array(26).fill(-1);
for (let i = 0; i < n; i++) {
last[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
}
let dig = 0;
let mx = 26;
// ans for storing resultant string
// ans1 for leftout and ans2 for picked up
let ans = s, ans1 ="" , ans2 = "";
for (let i = 0; i < n; i++) {
// For every i we will find its
// last occurrence last[dig]
while (dig < 26 && i > last[dig])
dig++;
if (dig == mx) {
let ans3 = ans2, ans4;
for (let j = 1; j < n; j++) {
// Adding the character
if (s.charCodeAt(j) == ('a'.charCodeAt(0) + mx)) {
ans4 += s[j];
}
else {
ans3 += s[j];
}
}
// Remove the other half and
// store the substring upto i
ans2 += s.substring(0,i);
// Find out the minimum
// and put it into ans
ans = ans1;
if(ans2 > ans4 + ans3)
ans2 = ans4 + ans3;
if(ans > ans2)
ans = ans2;
break;
}
else if (dig > mx) {
if(ans > ans1 + ans2 + s.substring(0,i))
ans = ans1 + ans2 + s.substring(0,i)
break;
}
// ans1 holds value retaining values
if (s.charCodeAt(i) == ('a'.charCodeAt(0) + dig)) {
ans1 += s[i];
}
else {
if (mx == 26)
mx = (s.charCodeAt(i) - 'a'.charCodeAt(0));
ans2 += s[i];
}
// Corner cases
if (i == n - 1){
if(ans > ans1 + ans2)
ans = ans1 + ans2;
}
}
// Return the ans
return ans;
}
// Driver code
let N = 3;
let s = "asa";
// Function call
document.write(LexMin(N, s),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
aas
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemantrathore2705 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA