[Solved] Find Lexicographically Smallest and Largest Substring

Problem Statement: You are given a string (says ‘s’),  and an integer ( says ‘k’). Write a program to find the lexicographically smallest and largest substring from given string ‘s’ of the length ‘k’.

Basically you have to find out all the sub-strings and then sort them in lexicographical order.

Some times lexicography order is also called an alphabetical order or dictionary order.

Lexicographically ordered characters:

A < B < C.......<  Y <  Z  <  a  <  b < .......< y < z

Note: Block letters come first in the lexicographic order and then small letters.

Example:  
Kite < King
kite > King

Lexicographically Smallest and Largest substring

Example

Given String: csestack

Lexicographically Smallest Substring: "ack"
Lexicographically Largest Substring: "tac"

Explanation

Suppose you’re given a String s=”csestack” and given the integer k=3.

Here, integer k=3 denotes the length of  possible substrings from the given string .

The following are the possible substrings derived from the given string.

["cse", "ses", "est", "sta", "tac", "ack"]

Sort the list of sub-strings in lexicographical order.

['ack', 'cse', 'est', 'ses', 'sta', 'tac']

The first element in the sorted list is the lexicographically smallest substring and the last element in the list is the lexicographically largest substring.

Algorithm

• Find all the sub-strings of the given length from the given string.
• Sort all the sub-strings in lexicographical order.
• Find the smallest lexical order element as the first element in the sorted list of the substring.
• Find the largest lexical order element as the last element in the sorted list of sub-string.

Python Program

Implementing above algorithm in Python is very easy as we can use the built in functions.

Here we are using,

• list comprehensions technique to find all the sub-string of length ‘k’
• sort() method to sort the list of sub-string in lexical order.
• string formatting for printing the smallest and largest lexicological ordered sub-string.

Python code:

str_given = 'csestack'
k = 3

#find all the substrings of lenght 'k'
len_str = len(str_given)
list_sub = [str_given[i:i+3] for i in range(len_str-2)]

#sort the list of the substring in lexical order
list_sub.sort()

#print smallest and largest 
#lexicographically ordered substring
print(f"Lexicographically  Smallest Substring: {list_sub[0]}")
print(f"Lexicographically  Largest Substring: {list_sub[-1]}")

Output:

Lexicographically Smallest Substring: ack
Lexicographically Largest Substring: tac

Let’s implement this logic by writing Java program for it.

Java Program

Implementing the same logic in Java is a bit difficult in Java as compared to Python. Here we are not using any inbuilt functions, rather implementing complete logic from Java basics.

Here we are using,

• flow-control statements like for loop, if-else, continue, break
• Java string methods like length(), substring()

Java Code:

import java.util.Scanner;

public class Solution {

    //function to print smallest and largest 
    //lexicographical ordered substring
    public static void getSmallestAndLargest(String s, int k) {
        String smallest = "";
        String largest = "";
        String arr[]= new String[s.length()-k+1];

        for (int i=0;i<s.length()-k+1;i++){
             arr[i]=s.substring(i,i+k);
        }

        for(int j=0; j<arr.length-1;j++){
            for(int g=0; g<arr.length-1 ; g++){
                String p=arr[g];
                String q=arr[g+1];
                boolean t=true;
                String temp="";
                for (int w=0; w<k;w++){
                      char pkaCharacter=p.charAt(w);
                      int b=(int) pkaCharacter;

                      char qkaCharacter=q.charAt(w);
                      int c=(int)  qkaCharacter;

                      if(b==c) continue;
                      else if(b>c){
                           t=false;
                           break;
                          }
                      else if(b<c){
                           t=true;
                           break;
                          }
                }

                if(t==false) {
                    temp=arr[g+1];
                    arr[g+1]=arr[g];
                    arr[g]=temp;
                }
                else{ continue;}
            }
        }
        smallest+=arr[0];
        largest+=arr[arr.length-1];
        System.out.println(smallest);
        System.out.println(largest);
    }
    
    //driving function
    public static void main(String[] args) 
    { 
        String str = "csestack"; 
        int k = 3; 
        getSmallestAndLargest(str, k); 
    } 
}

Output:

ack
tac

If you want to improve your coding skills, I would recommend you to practice solving coding challenge questions asked in coding interview rounds.

This is all about writing a program to find the lexicographically smallest and largest substring in Java and Python. From these coding examples, I hope you learn to sort strings in lexicographic order.