Minimum size lexicographically smallest string which is not a substring of given string

0 0 6 minutes read

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 = “zambiatek”
Output: a

Input: S = “abcd”
Output: e

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

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:
- For the current string at the front of the queue, check if it occurs in the given string or not.
- If it occurs in the given string, then append all characters from ‘a‘ to ‘z‘ individually and push them back into the queue, else print the current string and return.

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.

Output

ad

Time Complexity: O(N² * log N)
Auxiliary Space: O(N²)

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 zambiatek!