Given a string S, the task is to find the lexicographically shortest string of length less than or equal to K which is not a substring of the given string. If not possible, print -1.
Examples:
Input: S = zxabcehgf, K = 2
Output: d
Explanation: Lexicographically, the shortest string which is not a substring of a given string is d.Input: S = sdhaacbdefghijklmnopqrstuvwxyz, K = 3
Output: ab
Approach: The problem can be solved by finding all the substrings of given string S which have length less than or equal to K. Then start from the lexicographically smallest string ‘a‘, and keep forming the next string till we do not find the answer. Follow the steps below to solve the problem.
- Initialize a set of strings, say st, to store all the substrings of length at most K.
- Iterate from 1 to K to create all strings possible lengths from 1 to K.
- Check if the current string formed is present in the set or not. If not, then print it and return.
- Otherwise, form the next lexicographical string and repeat the process until an answer is found.
Below is the implementation of the above approach.
C++
// C++ implementation for above approach#include <bits/stdc++.h>using namespace std;// Function to return a set of all// substrings of given string which have// length less than or equal to kset<string> presentSubstring(string s, int k){ set<string> st; int n = s.length(); for (int i = 0; i < n; i++) { string s1 = ""; for (int j = 0; j < k && i + j < n; j++) { s1.push_back(s[i + j]); st.insert(s1); } } return st;}// Function to print the lexicographically// smallest substring of length atmost k// which is not present in given string sstring smallestSubstring(string s, int k){ set<string> st; // All substrings of length atmost k // present in string s are stored in // this set st = presentSubstring(s, k); int index; // Loop to change length of substring for (int len = 1; len <= k; len++) { // String with length=len which has // all characters as 'a' string t(len, 'a'); while (true) { // If the substrings set does // not contain this string then // we have found the answer if (st.count(t) == 0) { return t; } index = len - 1; // Changing the likes of 'azz' // and 'daz' to 'baa' and 'dba' // respectively while (index >= 0 && t[index] == 'z') { t[index] = 'a'; index--; } if (index >= 0) t[index]++; // Reached a string like 'zz' // or 'zzz' increase the length // of the substring else break; } } return "-1";}// Driver Codeint main(){ // Given Input string s = "sdhaacbdefghijklmnopqrstuvwxyz"; int K = 3; // Function Call cout << smallestSubstring(s, K) << endl; return 0;} |
Java
// Java implementation for above approachimport java.util.*;class GFG{// Function to return a set of all// subStrings of given String which have// length less than or equal to kstatic HashSet<String> presentSubString(String s, int k){ HashSet<String> st = new HashSet<String>(); int n = s.length(); for (int i = 0; i < n; i++) { String s1 = ""; for (int j = 0; j < k && i + j < n; j++) { s1 += s.charAt(i + j); st.add(s1); } } return st;}// Function to print the lexicographically// smallest subString of length atmost k// which is not present in given String sstatic String smallestSubString(String s, int k){ HashSet<String> st = new HashSet<String>(); // All subStrings of length atmost k // present in String s are stored in // this set st = presentSubString(s, k); int index; // Loop to change length of subString for (int len = 1; len <= k; len++) { // String with length=len which has // all characters as 'a' String t = ""; for(int i=0;i<len;i++) t+='a'; while (true) { // If the subStrings set does // not contain this String then // we have found the answer if (!st.contains(t)) { return t; } index = len - 1; // Changing the likes of 'azz' // and 'daz' to 'baa' and 'dba' // respectively while (index >= 0 && t.charAt(index) == 'z') { t=t.substring(0,index)+'a'+t.substring(index+1); index--; } if (index >= 0) t=t.substring(0,index)+ (char)((t.charAt(index))+1) + t.substring(index+1); // Reached a String like 'zz' // or 'zzz' increase the length // of the subString else break; } } return "-1";}// Driver Codepublic static void main(String[] args){ // Given Input String s = "sdhaacbdefghijklmnopqrstuvwxyz"; int K = 3; // Function Call System.out.print(smallestSubString(s, K) +"\n");}}// This code is contributed by shikhasingrajput |
Python3
# Python 3 implementation for above approach# Function to return a set of all# substrings of given string which have# length less than or equal to kdef presentSubstring(s, k): st = set() n = len(s) s = list(s) for i in range(n): s1 = "" j = 0 while(j < k and i + j < n): s1 += s[i + j] st.add(s1) j += 1 s = ''.join(s) return st# Function to print the lexicographically# smallest substring of length atmost k# which is not present in given string sdef smallestSubstring(s, k): st = set() # All substrings of length atmost k # present in string s are stored in # this set st = presentSubstring(s, k) index = 0 # Loop to change length of substring for len1 in range(1,k+1,1): # String with length=len which has # all characters as 'a' t = [] for x in range(len1): t.append('a') while (True): # If the substrings set does # not contain this string then # we have found the answer if (''.join(t) not in st): return ''.join(t) index = len1 - 1 # Changing the likes of 'azz' # and 'daz' to 'baa' and 'dba' # respectively while (index >= 0 and t[index] == 'z'): t[index] = 'a' index -= 1 if (index >= 0): t[index] = chr(ord(t[index])+1) # Reached a string like 'zz' # or 'zzz' increase the length # of the substring else: break return "-1"# Driver Codeif __name__ == '__main__': # Given Input s = "sdhaacbdefghijklmnopqrstuvwxyz" K = 3 # Function Call print(smallestSubstring(s, K)) # This code is contributed by ipg2016107. |
C#
// C# implementation for above approachusing System;using System.Collections.Generic;class GFG { // Function to return a set of all // substrings of given string which have // length less than or equal to k static HashSet<string> presentSubstring(string s, int k) { HashSet<string> st = new HashSet<string>(); int n = s.Length; for (int i = 0; i < n; i++) { string s1 = ""; for (int j = 0; j < k && i + j < n; j++) { s1 += s[i + j]; st.Add(s1); } } return st; } // Function to print the lexicographically // smallest substring of length atmost k // which is not present in given string s static string smallestSubstring(string s, int k) { HashSet<string> st = new HashSet<string>(); // All substrings of length atmost k // present in string s are stored in // this set st = presentSubstring(s, k); int index; // Loop to change length of substring for (int len = 1; len <= k; len++) { // String with length=len which has // all characters as 'a' string t = ""; for (int i = 0; i < len; i++) t += 'a'; while (true) { // If the substrings set does // not contain this string then // we have found the answer if (st.Contains(t)==false) { return t; } index = len - 1; // Changing the likes of 'azz' // and 'daz' to 'baa' and 'dba' // respectively while (index >= 0 && t[index] == 'z') { t = t.Substring(0, index) + 'a' + t.Substring(index + 1); index--; } if (index >= 0) { t = t.Substring(0, index) + Convert.ToChar((int)t[index] + 1) + t.Substring(index + 1); } // Reached a string like 'zz' // or 'zzz' increase the length // of the substring else break; } // t += 'b'; } return "-1"; } // Driver Code public static void Main() { // Given Input string s = "sdhaacbdefghijklmnopqrstuvwxyz"; int K = 3; // Function Call Console.Write(smallestSubstring(s, K)); }}// This code is contributed by ipg2016107. |
Javascript
<script>// Javascript implementation for above approach// Function to return a set of all// substrings of given string which have// length less than or equal to kfunction presentSubstring(s, k) { let st = new Set(); let n = s.length; s = s.split(""); for (let i = 0; i < n; i++) { let s1 = ""; for (let j = 0; j < k && i + j < n; j++) { s1 += s[i + j]; st.add(s1); } } return st;}// Function to print the lexicographically// smallest substring of length atmost k// which is not present in given string sfunction smallestSubstring(s, k) { let st = new Set(); // All substrings of length atmost k // present in string s are stored in // this set st = presentSubstring(s, k); let index = 0; // Loop to change length of substring for (let len = 1; len <= k; len++) { // String with length=len which has // all characters as 'a' let t = new Array(len).fill("a"); while (true) { // If the substrings set does // not contain this string then // we have found the answer if (!st.has(t.join(""))) { return t.join(""); } index = len - 1; // Changing the likes of 'azz' // and 'daz' to 'baa' and 'dba' // respectively while (index >= 0 && t[index] == "z") { t[index] = "a"; index--; } if (index >= 0) t[index] = String.fromCharCode(t[index].charCodeAt(0) + 1); // Reached a string like 'zz' // or 'zzz' increase the length // of the substring else break; } } return "-1";}// Driver Code// Given Inputlet s = "sdhaacbdefghijklmnopqrstuvwxyz";let K = 3;// Function Calldocument.write(smallestSubstring(s, K));// This code is contributed by _saurabh_jaiswal.</script> |
Output
ab
Time Complexity: O(K*N)
Auxiliary Space: O(K*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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
