483. Find Lexicographically smallest or largest substring of size k

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

Example:

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"

Approach:

1. Base case: If given string length is less than k the print "invalid input" and return.
2. Idea to maintain two substrings of size k, current_substring and smallest_substring.
3. Initialize current_substring = smallest_substring = first k characters of input string. 
4. 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.
5. See the code below for better understanding.

Output: 

Given Input: horizon, k=2
Smallest Lexicographically SubString: ho

Related Problems:

- Sort Names by their Last Names Beginner
- Minimum number of times String A is repeated to such that B is substring of A Beginner
- Check If Student is eligible for an Attendance Reward Beginner
- Check If String has All Unique Characters Beginner
- Generate All String Permutations Hard