Lexicographically shortest string of length at most K which is not a substring of given String | Java 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
import java . util . * ; class GFG { 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 . charAt ( i + j ) ; st . add ( s1 ) ; } } return st ; } static String smallestSubString ( String s , int k ) { HashSet < String > st = new HashSet < String > ( ) ; st = presentSubString ( s , k ) ; int index ; for ( int len = 1 ; len <= k ; len ++ ) { String t = " " ; for ( int i = 0 ; i < len ; i ++ ) t += ' a ' ; while ( true ) { if ( ! st . contains ( t ) ) { return t ; } index = len - 1 ; 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 ) ; else break ; } } return " - 1" ; } public static void main ( String [ ] args ) { String s = " sdhaacbdefghijklmnopqrstuvwxyz " ; int K = 3 ; System . out . print ( smallestSubString ( s , K ) + "NEW_LINE"); } }