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: aEntrada: 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:
A continuación se muestra la implementación del enfoque anterior:
C++
// 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
// 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
Python3
# 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#
// 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
// 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 2 * log N)
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA