Menor Mayor (que S) String de longitud K cuyas letras son un subconjunto de S

Dada una string S de longitud N que consta de letras inglesas minúsculas y un número entero K. Encuentre la string T lexicográficamente más pequeña de longitud K, tal que su conjunto de letras sea un subconjunto del conjunto de letras de S y T sea lexicográficamente mayor que S Nota : El conjunto de letras es un conjunto, no un conjunto múltiple. Por ejemplo, el conjunto de letras de abadaba es {a, b, d}.
Ejemplos:

 
Entrada: S = “abc”, K = 3 
Salida: T = “aca” 
Explicación : La lista de strings T de longitud 3, tal que el conjunto de letras de T es un subconjunto de letras de S es como sigue: “aaa ”, “aab”, “aac”, “aba”, “abb”, “abc”, “aca”, “acb”, …. Entre ellos, los que lexicográficamente son mayores que “abc”: 
“aca”, “acb”,…. De esos, el más pequeño lexicográficamente es «aca».
Entrada: S = “abc”, K = 2 
Salida: T = “ac”

Una solución simple es probar todas las strings de longitud k en orden creciente. Para cada string, verifique si es mayor que S, si es así, devuélvalo.
A continuación se muestra un método eficiente para resolver este problema.
Consideremos dos casos: 
1. Si N < K : para este caso, podemos simplemente copiar la string S a la string T para hasta N caracteres y para los caracteres restantes (K – N) podemos agregar el carácter mínimo (valor ASCII mínimo). ) en la string S a la string T (K – N) veces ya que tenemos que encontrar la string lexicográficamente más pequeña que sea justo mayor que la string S.
2. Si N ≥ K: Para este caso, necesitamos copiar la string S a la string T para hasta K caracteres y luego para la string T al iterar en dirección inversa, tenemos que reemplazar todos esos caracteres por algún carácter hasta que la string T se convierta en la string lexicográficamente más pequeña mayor que string S. Para esto podemos hacer lo siguiente: 
 

1. Almacene los caracteres de la string S en un conjunto STL (por supuesto, en orden)
2. Copie la string S a la string T hasta K caracteres.
3. Iterando en dirección inversa, encuentre un carácter (deje que se encuentre en la posición ‘p’) para el cual exista algún carácter que tenga un mayor valor ASCII en el conjunto.
4. Reemplace este carácter con el que se encuentra en el conjunto.
5. Reemplace todos los caracteres con el carácter mínimo después de (p + 1) ^el índice hasta ^el índice K.

Ilustración: Sea S = “bcegikmyyy”, N = 10, K = 9. Conjunto = { b, c, e, g, i, k, m, y }. Copie la string S a T hasta K caracteres T = «bcegikmyy». Luego, iterando en dirección inversa, primero tenemos ‘y’ pero no hay un carácter mayor que ‘y’ en el conjunto, así que siga adelante. Nuevamente tenemos ‘y’, siga adelante ahora tenemos ‘m’ para el cual hay un carácter mayor ‘y’ en el conjunto. Reemplace ‘m’ con ‘y’ y luego, después de ‘m’ en dirección hacia adelante, reemplace todos los caracteres con un carácter mínimo, es decir, ‘b’. Por tanto, la string T se convierte en T = “bcegikybb”;
 

/* CPP Program to find the lexicographically
   smallest string T greater than S whose
   letters are subset of letters of S */
#include <bits/stdc++.h>
 
using namespace std;
 
// function to find the lexicographically
// smallest string greater than S
string findString(string S, int N, int K)
{
    // stores minimum character
    char minChar = 'z';
 
    // stores unique characters of
    // string in sorted order
    set<char> found;
 
    // Loop through to find the minimum character
    // and stores characters in the set
    for (int i = 0; i < N; i++) {
        found.insert(S[i]);
        if (S[i] < minChar)
            minChar = S[i];
    }
 
    string T;
 
    // Case 1: If N < K
    if (N < K) {
 
        // copy the string S upto N characters
        T = S;
 
        // append minChar to make the remaining
        // characters
        for (int i = 0; i < (K - N); i++)
            T += minChar;
    }
 
    // Case 2 :  If N >= K
    else {
        T = "";
 
        // copy the string S upto K characters
        for (int i = 0; i < K; i++)
            T += S[i];
 
        int i;
 
        // an iterator to the set
        set<char>::iterator it;
 
        // iterating in reverse direction
        for (i = K - 1; i >= 0; i--) {
 
            // find the current character in the set
            it = found.find(T[i]);
 
            // increment the iterator
            it++;
 
            // check if some bigger character exists in set
            if (it != found.end())
                break;
        }
 
        // Replace current character with that found in set
        T[i] = *it;
 
        // Replace all characters after with minChar
        for (int j = i + 1; j < K; j++)
            T[j] = minChar;
    }
 
    return T;
}
 
// Driver Code to test the above function
int main()
{
    string S = "abc";
    int N = S.length();
 
    // Length of required string
    int K = 3;
 
    string T = findString(S, N, K);
    cout << "Lexicographically Smallest String "
            "greater than " << S
         << " is " << T << endl;
    return 0;
}

''' Python 3 Program to find the lexicographically
smallest string T greater than S whose
letters are subset of letters of S '''
 
# function to find the lexicographically
# smallest string greater than S
def findString(S,  N,  K):
 
    # stores minimum character
    minChar = 'z'
 
    # stores unique characters of
    # string in sorted order
    found = set([])
 
    # Loop through to find the minimum character
    # and stores characters in the set
    for i in range(N):
        found.add(S[i])
        if (S[i] < minChar):
            minChar = S[i]
 
    T = ""
 
    # Case 1: If N < K
    if (N < K):
        # copy the string S upto N characters
        T = S
 
        # append minChar to make the remaining
        # characters
        for i in range((K - N)):
            T += minChar
 
    # Case 2 : If N >= K
    else:
        T = ""
 
        # copy the string S upto K characters
        for i in range(K):
            T += S[i]
 
        T = list(T)
        # iterating in reverse direction
        for i in range(K - 1, -1, -1):
 
            # find the current character in the set
            if(T[i] in found):
                it = T[i]
 
            # increment the iterator
            it = chr(ord(it)+1)
 
            # check if some bigger character exists in set
            if (it in found):
                break
 
        # Replace current character with that found in set
        T[i] = it
 
        # Replace all characters after with minChar
        for j in range(i + 1, K):
            T[j] = minChar
 
    return T
 
# Driver Code to test the above function
if __name__ == "__main__":
 
    S = "abc"
    N = len(S)
 
    # Length of required string
    K = 3
 
    T = findString(S, N, K)
    print("Lexicographically Smallest String "
          "greater than " + S + " is " + "".join(T))
 
    # This code s contributed by ukasp.

Lexicographically Smallest String greater than abc is aca

Complejidad de tiempo: O(N + K) , donde N es la longitud de la string dada y K es la longitud de la string requerida.