Minimum size lexicographically smallest string which is not a substring of given string
Given a string s, the task is to find the lexicographically smallest string of minimum characters that do not exist as a substring in S.
Examples:
Input: S = “aabacdefghijklmnopqrstuvwxyz”
Output: ad
Explanation: All the single digit strings from [a-z] occur in the given string and in two character strings, strings {aa, ab, ac} occur but “ad” is not present in the given string.Input: S = “w3wiki”
Output: aInput: S = “abcd”
Output: e
Approach: The problem can be solved using BFS (Breadth-First Search) algorithm. Generate all strings in lexicographical order and check if it exists as a substring in the given string or not. Follow the steps below to solve the problem:
- Initialize a set, say collection to store all substrings of the given string s.
- Iterate over the characters of the given string S and store all substrings into the collection.
- Initialize a queue, say stringQueue, to generate strings in lexicographical order.
- Initially, push all single digits strings from ‘a‘ to ‘z‘ into the queue.
- Iterate while the queue is not empty:
Below is the implementation of the above approach:
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
Time Complexity: O(N2 * log N)
Auxiliary Space: O(N2)