Tamaño mínimo lexicográficamente la string más pequeña que no es una substring de la string dada

Dada una string s , la tarea es encontrar la string lexicográficamente más pequeña de caracteres mínimos que no existen como una substring en S .

Ejemplos: 

Entrada: S = “aabacdefghijklmnopqrstuvwxyz”
Salida: ad
Explicación: Todas las strings de un solo dígito de [az] aparecen en la string dada y en strings de dos caracteres, las strings {aa, ab, ac} aparecen pero “ad” no está presente en la string dada.

Entrada: S = «geeksforgeeks»
Salida: a

Entrada: S = “abcd”
Salida: e

Enfoque: el problema se puede resolver utilizando el algoritmo BFS (búsqueda primero en anchura). Genere todas las strings en orden lexicográfico y verifique si existe como una substring en la string dada o no. Siga los pasos a continuación para resolver el problema:

• Inicialice un conjunto , digamos una colección para almacenar todas las substrings de las strings dadas .
• Iterar sobre los caracteres de la string S dada y almacenar todas las substrings en la colección.
• Inicialice una cola , digamos stringQueue , para generar strings en orden lexicográfico.
• Inicialmente, inserte todas las strings de un solo dígito de ‘ a ‘ a ‘ z ‘ en la cola .
• Iterar mientras la cola no está vacía:
  • Para la string actual al principio de la cola, verifique si aparece en la string dada o no.
  • Si ocurre en la string dada , agregue todos los caracteres de ‘ a ‘ a ‘ z ‘ individualmente y vuelva a colocarlos en la cola ; de lo contrario, imprima la string actual y regrese .

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the lexicographically
// smallest string of minimum characters
// not present as substring in string S
void lexicographicalSmallestString(string& S, int n)
{
    // Set which stores all substrings
    // of the string S
    set<string> collection;
 
    // Constructing all substrings of S
    for (int i = 0; i < n; ++i) {
        string cur;
        for (int j = i; j < n; ++j) {
            cur.push_back(S[j]);
 
            // Inserting the current
            // substring to set
            collection.insert(cur);
        }
    }
 
    queue<string> q;
 
    // Initializing BFS queue
    for (int i = 0; i < 26; ++i) {
        q.push(string(1, i + 'a'));
    }
 
    // Loop for the BFS Traversal
    while (!q.empty()) {
 
        // Stores the current
        // lexicographically smallest
        // string of min characters
        auto cur = q.front();
        q.pop();
 
        // If the current string is
        // not present as a substring
        // of the given string
        if (collection.find(cur) == collection.end()) {
 
            // Print Answer
            cout << cur << endl;
            return;
        }
 
        // Append characters from [a-z]
        // to the back of string cur
        // and push into the queue.
        for (int i = 0; i < 26; ++i) {
            cur.push_back(i + 'a');
            q.push(cur);
            cur.pop_back();
        }
    }
}
 
// Driver Code
int main()
{
    string S = "aabacdefghijklmnopqrstuvwxyz";
    int N = S.length();
 
    lexicographicalSmallestString(S, N);
}

// Java implementation of the above approach
import java.util.*;
 
class GFG{
 
// Function to find the lexicographically
// smallest String of minimum characters
// not present as subString in String S
static void lexicographicalSmallestString(char[] S, int n)
{
   
    // Set which stores all subStrings
    // of the String S
    HashSet<String> collection = new HashSet<String>();
 
    // Constructing all subStrings of S
    for (int i = 0; i < n; ++i) {
        String cur="";
        for (int j = i; j < n; ++j) {
            cur+=(S[j]);
 
            // Inserting the current
            // subString to set
            collection.add(cur);
        }
    }
 
    Queue<String> q = new LinkedList<String>();
 
    // Initializing BFS queue
    for (int i = 0; i < 26; ++i) {
        q.add(String.valueOf((char)((i + 'a'))));
    }
 
    // Loop for the BFS Traversal
    while (!q.isEmpty()) {
 
        // Stores the current
        // lexicographically smallest
        // String of min characters
        String cur = q.peek();
        q.remove();
 
        // If the current String is
        // not present as a subString
        // of the given String
        if (!collection.contains(cur)) {
 
            // Print Answer
            System.out.print(cur +"\n");
            return;
        }
 
        // Append characters from [a-z]
        // to the back of String cur
        // and push into the queue.
        for (int i = 0; i < 26; ++i) {
            cur+=String.valueOf((char)((i + 'a')));
            q.add(cur);
            cur=cur.substring(0,cur.length()-1);
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "aabacdefghijklmnopqrstuvwxyz";
    int N = S.length();
 
    lexicographicalSmallestString(S.toCharArray(), N);
}
}
 
// This code is contributed by shikhasingrajput

# python  implementation of the above approach
from queue import Queue
 
# Function to find the lexicographically
# smallest string of minimum characters
# not present as substring in string S
def lexicographicalSmallestString(S, n):
 
    # Set which stores all substrings
    # of the string S
    collection = set()
 
    # Constructing all substrings of S
    for i in range(0, n):
        cur = ""
        for j in range(i, n):
            cur += (S[j])
 
            # Inserting the current
            # substring to set
            collection.add(cur)
 
    q = Queue()
 
    # Initializing BFS queue
    for i in range(0, 26):
        q.put(chr(i + ord('a')))
 
    # Loop for the BFS Traversal
    while (not q.empty()):
 
        # Stores the current
        # lexicographically smallest
        # string of min characters
        cur = q.get()
 
        # If the current string is
        # not present as a substring
        # of the given string
        if (not (cur in collection)):
 
            # Print Answer
            print(cur)
            return
 
        # Append characters from [a-z]
        # to the back of string cur
        # and push into the queue.
        for i in range(0, 26):
            q.put((cur + chr(i+ord('a'))))
 
# Driver Code
if __name__ == "__main__":
 
    S = "aabacdefghijklmnopqrstuvwxyz"
    N = len(S)
 
    lexicographicalSmallestString(S, N)
 
    # This code is contributed by rakeshsahni

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
// Function to find the lexicographically
// smallest String of minimum characters
// not present as subString in String S
static void lexicographicalSmallestString(char[] S, int n)
{
   
    // Set which stores all subStrings
    // of the String S
    HashSet<String> collection = new HashSet<String>();
 
    // Constructing all subStrings of S
    for (int i = 0; i < n; ++i) {
        String cur = "";
        for (int j = i; j < n; ++j) {
            cur += (S[j]);
 
            // Inserting the current
            // subString to set
            collection.Add(cur);
        }
    }
 
    Queue<String> q = new Queue<String>();
 
    // Initializing BFS queue
    for (int i = 0; i < 26; ++i) {
        q.Enqueue(String.Join("",(char)((i + 'a'))));
    }
 
    // Loop for the BFS Traversal
    while (q.Count != 0) {
 
        // Stores the current
        // lexicographically smallest
        // String of min characters
        String cur = q.Peek();
        q.Dequeue();
 
        // If the current String is
        // not present as a subString
        // of the given String
        if (!collection.Contains(cur)) {
 
            // Print Answer
            Console.Write(cur +"\n");
            return;
        }
 
        // Append characters from [a-z]
        // to the back of String cur
        // and push into the queue.
        for (int i = 0; i < 26; ++i) {
            cur += String.Join("",(char)((i + 'a')));
            q.Enqueue(cur);
            cur=cur.Substring(0,cur.Length-1);
        }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    String S = "aabacdefghijklmnopqrstuvwxyz";
    int N = S.Length;
 
    lexicographicalSmallestString(S.ToCharArray(), N);
}
}
 
// This code is contributed by 29AjayKumar

// Javascript implementation of the above approach
 
// Function to find the lexicographically
// smallest string of minimum characters
// not present as substring in string S
function lexicographicalSmallestString(S, n)
{   
 
    // Set which stores all substrings
    // of the string S
    let collection = new Set();
 
    // Constructing all substrings of S
    for (let i = 0; i < n; ++i) {
        let cur = ""
        for (let j = i; j < n; ++j) {
            cur += S[j];
 
            // Inserting the current
            // substring to set
            collection.add(cur);
        }
    }
 
    let q = [];
 
    // Initializing BFS queue
    for (let i = 0; i < 26; ++i) {
        q.push(String.fromCharCode('a'.charCodeAt(0) + i));
    }
 
    // Loop for the BFS Traversal
    while (q.length) {
 
        // Stores the current
        // lexicographically smallest
        // string of min characters
        let cur = q[0];
        q.shift();
 
        // If the current string is
        // not present as a substring
        // of the given string
        if (!collection.has(cur)) {
 
            // Print Answer
            document.write(cur + '<br>');
            return;
        }
 
        // Append characters from [a-z]
        // to the back of string cur
        // and push into the queue.
        for (let i = 0; i < 26; ++i) {
            q.push(cur + (String.fromCharCode(i + 'a'.charCodeAt(0))));
        }
    }
}
 
// Driver Code
 
let S = "aabacdefghijklmnopqrstuvwxyz";
let N = S.length;
 
lexicographicalSmallestString(S, N);
 
// This code is contributed by gfgking.

ad

Complejidad de Tiempo: O(N ² * log N)
Espacio Auxiliar: O(N ² )