Given a string and number k, write a program to find the lexicographically smallest substring of size k.
Note: This problem can also be asked as find the lexicographically largest substring of size k
Input: "tutorial", k = 2 Output: Smallest Lexicographically SubString: "al" Input: "tutorial", k=3 Smallest Lexicographically SubString: "ial" Input: horizon, k=2 Smallest Lexicographically SubString: "ho"
- Base case: If given string length is less than k the print “invalid input” and return.
- Idea to maintain two substrings of size k, current_substring and smallest_substring.
- Initialize current_substring = smallest_substring = first k characters of input string.
- Now iterate through the input string from the k+1th character to the end of the string. During iteration include a next character in current_substring and exclude the first character from current_substring. Compare the current_substring with smallest_substring, if smallest_substring is smaller than current_substring, do smallestSubString = currSubString. Once the iteration is completed, smallestSubString will be our result.
- See the code below for better understanding.
Given Input: horizon, k=2 Smallest Lexicographically SubString: ho