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.

Complete Code:

Output: 

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

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.