This post is completed by 1 user

  • 0
 Add to List
Beginner

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: