Dada la string S y un entero positivo K , la tarea es encontrar lexicográficamente la string más grande posible utilizando como máximo K intercambios con la condición de que los índices que se intercambian deben ser impares o pares.
Ejemplos:
Entrada: S = «ancqz», K = 2
Salida: « zqcna »
Explicación: En un intercambio, podemos intercambiar los caracteres ‘n’ y ‘q’ ya que ambos están en índices pares (2 y 4 suponiendo una indexación basada en 1) . La string se convierte en «aqcnz». En el segundo intercambio, podemos intercambiar los caracteres ‘a’ y ‘z’ ya que ambos tienen índices impares. La string final «zqcna» es la lexicográficamente más grande posible usando 2 operaciones de intercambio.Nota: No podemos intercambiar, por ejemplo, ‘a’ y ‘n’ o ‘n’ y ‘z’ ya que uno de ellos estaría en un índice impar mientras que el otro estaría en un índice par.
Entrada: S = «geeksforgeeks», K = 3
Salida: « sreksfoegeekg «
Enfoque ingenuo: El enfoque ingenuo es trivial. Use el algoritmo codicioso para hacer que el índice actual sea máximo comenzando desde la izquierda seleccionando el máximo carácter posible que está a la derecha del índice actual y que también tiene la misma paridad de índice, es decir (impar si el índice actual es impar e incluso si el índice actual es impar). el índice actual es par). Repetir el mismo procedimiento como máximo K veces. La complejidad temporal de la aproximación será O(N 2 ) .
Enfoque eficiente: el enfoque anterior se puede mejorar utilizando una cola de prioridad . Siga los pasos a continuación para resolver el problema:
- Cree dos colas de prioridad, una para caracteres de índice impares y otra para caracteres de índice pares.
- Itere sobre los caracteres en la string , si el carácter de índice par viene, busque el índice que es mayor que el índice actual y el carácter más grande que el carácter actual en la cola de prioridad que contiene caracteres pares. Si hay alguno, intercambiar los dos caracteres empujar el carácter actual y el índice que encontramos en la cola de prioridad .
- El mismo procedimiento se debe seguir cuando viene el carácter impar.
- Si K se convierte en 0 , termina el bucle.
- La string resultante será la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function which returns
// the largest possible string
string lexicographicallyLargest(string S, int K)
{
// Finding length of the string
int n = S.length();
// Creating two priority queues of pairs
// for odd and even indices separately
priority_queue<pair<char, int> > pqOdd, pqEven;
// Storing all possible even
// indexed values as pairs
for (int i = 2; i < n; i = i + 2) {
// Stores pair as {character, index}
pqEven.push(make_pair(S[i], i));
}
// Storing all possible odd indexed
// values as pairs
for (int i = 3; i < n; i = i + 2) {
// Stores pair as {character, index}
pqOdd.push(make_pair(S[i], i));
}
for (int i = 0; i < n; i++) {
// For even indices
if (i % 2 == 0) {
// Removing pairs which
// cannot be used further
while (!pqEven.empty()
and pqEven.top().second <= i)
pqEven.pop();
// If a pair is found whose index comes after
// the current index and its character is
// greater than the current character
if (!pqEven.empty()
and pqEven.top().first > S[i]) {
// Swap the current index with index of
// maximum found character next to it
swap(S[i], S[pqEven.top().second]);
int idx = pqEven.top().second;
pqEven.pop();
// Push the updated character at idx index
pqEven.push({ S[idx], idx });
K--;
}
}
// For odd indices
else {
// Removing pairs which cannot
// be used further
while (!pqOdd.empty()
and pqOdd.top().second <= i)
pqOdd.pop();
// If a pair is found whose index comes after
// the current index and its character is
// greater than the current character
if (!pqOdd.empty()
and pqOdd.top().first > S[i]) {
// Swap the current index with index of
// maximum found character next to it
swap(S[i], S[pqOdd.top().second]);
int idx = pqOdd.top().second;
pqOdd.pop();
// Push the updated character at idx index
pqOdd.push({ S[idx], idx });
K--;
}
}
// Breaking out of the loop if K=0
if (K == 0)
break;
}
return S;
}
// Driver Code
int main()
{
// Input
string S = "geeksforgeeks";
int K = 2;
// Function Call
cout << lexicographicallyLargest(S, K);
return 0;
}
sreksfoegeekg
Complejidad temporal: O(NlogN)
Espacio auxiliar:EN)