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 = “neveropen”
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 Svoid 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 Codeint main(){ string S = "aabacdefghijklmnopqrstuvwxyz"; int N = S.length(); lexicographicalSmallestString(S, N);} |
Java
// Java implementation of the above approachimport java.util.*;class GFG{// Function to find the lexicographically// smallest String of minimum characters// not present as subString in String Sstatic 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 Codepublic 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 approachfrom queue import Queue# Function to find the lexicographically# smallest string of minimum characters# not present as substring in string Sdef 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 Codeif __name__ == "__main__": S = "aabacdefghijklmnopqrstuvwxyz" N = len(S) lexicographicalSmallestString(S, N) # This code is contributed by rakeshsahni |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;public class GFG{// Function to find the lexicographically// smallest String of minimum characters// not present as subString in String Sstatic 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 Codepublic 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 Sfunction 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 Codelet S = "aabacdefghijklmnopqrstuvwxyz";let N = S.length;lexicographicalSmallestString(S, N);// This code is contributed by gfgking. |
Output
ad
Time Complexity: O(N2 * log N)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!