La string lexicográficamente más pequeña que no es una subsecuencia de la string dada

Dada una string S , la tarea es encontrar la string que sea lexicográficamente más pequeña y no una subsecuencia de la string S dada .

 Ejemplos:

Entrada: S = “abcdefghijklmnopqrstuvwxyz”
Salida: 
aa
Explicación:
La string “aa” es la string lexicográficamente más pequeña que no está presente en la string dada como una subsecuencia.

Entrada: S = “aaaa”
Salida: 
aaab
Explicación:
La string “aaa” es la string lexicográficamente más pequeña que no está presente en la string dada como una subsecuencia.

Enfoque: La idea para resolver el problema dado es encontrar la frecuencia del carácter ‘a’ en la string dada (por ejemplo, f ). Si el valor de f es menor que la longitud de la string , entonces la respuesta sería la string formada al concatenar ‘a’ f+1 veces como aaa….(f+1 veces) será la string lexicográficamente más pequeña requerida que no es una subsecuencia. De lo contrario, la respuesta sería la string formada al concatenar ‘ a’ (f-1 veces) y ‘b’ al final de la string.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find lexicographically smallest string that
// is not a subsequence of S
string smallestNonSubsequence(string S, int N)
{
    // variable to store frequency of 'a'
    int freq = 0;
    // calculate frequency of 'a'
    for (int i = 0; i < N; i++)
        if (S[i] == 'a')
            freq++;
    // Initialize string consisting of freq number of 'a'
    string ans(freq, 'a');
    // change the last digit to 'b'
    if (freq == N)
        ans[freq - 1] = 'b';
    // add another 'a' to the string
    else
        ans += 'a';
    // return the answer string
    return ans;
}
// Driver code
int main()
{
    // Input
    string S = "abcdefghijklmnopqrstuvwxyz";
    int N = S.length();
 
    // Function call
    cout << smallestNonSubsequence(S, N) << endl;
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
 
// Function to find lexicographically smallest string that
// is not a subsequence of S
static String smallestNonSubsequence(String S, int N)
{
   
    // variable to store frequency of 'a'
    int freq = 0;
   
    // calculate frequency of 'a'
    for (int i = 0; i < N; i++)
        if (S.charAt(i) == 'a')
            freq++;
   
    // Initialize string consisting of freq number of 'a'
 String ans="";
    for(int i = 0; i < f req; i++){
        ans += 'a';
    }
   
    // change the last digit to 'b'
    if (freq == N)
       ans = ans.replace(ans.charAt(freq - 1), 'b');
   
    // add another 'a' to the string
    else
        ans += 'a';
   
    // return the answer string
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
    String S = "abcdefghijklmnopqrstuvwxyz";
    int N = S.length();
 
    // Function call
    System.out.println(smallestNonSubsequence(S, N));
    }
}
 
// This code is contributed by SoumikMondal

# Python3 program for the above approach
 
# Function to find lexicographically smallest
# string that is not a subsequence of S
def smallestNonSubsequence(S, N):
     
    # Variable to store frequency of 'a'
    freq = 0
     
    # Calculate frequency of 'a'
    for i in range(N):
        if (S[i] == 'a'):
            freq += 1
             
    # Initialize string consisting
    # of freq number of 'a'
    ans = ""
    for i in range(freq):
        ans += 'a'
 
    # Change the last digit to 'b'
    if (freq == N):
        ans = ans.replace(ans[freq - 1], 'b')
         
    # Add another 'a' to the string
    else:
        ans += 'a'
         
    # Return the answer string
    return ans
 
# Driver code
if __name__ == '__main__':
     
    # Input
    S = "abcdefghijklmnopqrstuvwxyz"
    N = len(S)
 
    # Function call
    print(smallestNonSubsequence(S, N))
     
# This code is contributed by SURENDRA_GANGWAR

<script>
 
// JavaScript program for the above approach
 
// Function to find lexicographically smallest string that
// is not a subsequence of S
function smallestNonSubsequence(S,N)
{
 
    // variable to store frequency of 'a'
    let freq = 0;
     
    // calculate frequency of 'a'
    for (let i = 0; i < N; i++)
        if (S[i] == 'a')
            freq++;
             
    // Initialize string consisting of freq number of 'a'
    let ans = new Array(freq).fill('a').join('');
    // change the last digit to 'b'
    if (freq == N)
        ans[freq - 1] = 'b';
         
    // add another 'a' to the string
    else
        ans += 'a';
         
    // return the answer string
    return ans;
}
 
// Driver code
 
// Input
let S = "abcdefghijklmnopqrstuvwxyz";
let N = S.length;
 
// Function call
document.write(smallestNonSubsequence(S, N),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

aa

Complejidad temporal: O(N)
Espacio auxiliar: O(1)