Lexicographically shortest string of length at most K which is not a substring of given String | C ++ implementation for above approach ; Function to return a set of all substrings of given string which have length less than or equal to k ; Function to print the lexicographically smallest substring of length atmost k which is not present in given string s ; All substrings of length atmost k present in string s are stored in this set ; Loop to change length of substring ; String with length = len which has all characters as ' a ' ; If the substrings set does not contain this string then we have found the answer ; Changing the likes of ' azz ' and ' daz ' to ' baa ' and ' dba ' respectively ; Reached a string like ' zz ' or ' zzz ' increase the length of the substring ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; set < 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 ; } string smallestSubstring ( string s , int k ) { set < string > st ; st = presentSubstring ( s , k ) ; int index ; for ( int len = 1 ; len <= k ; len ++ ) { string t ( len , ' a ' ) ; while ( true ) { if ( st . count ( t ) == 0 ) { return t ; } index = len - 1 ; while ( index >= 0 && t [ index ] == ' z ' ) { t [ index ] = ' a ' ; index -- ; } if ( index >= 0 ) t [ index ] ++ ; else break ; } } return " - 1" ; } int main ( ) { string s = " sdhaacbdefghijklmnopqrstuvwxyz " ; int K = 3 ; cout << smallestSubstring ( s , K ) << endl ; return 0 ; }