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
Table of Contents
Given String: csestack Lexicographically Smallest Substring: "ack" Lexicographically Largest Substring: "tac"
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.
Implementing above algorithm in Python is very easy as we can use the built in functions.
Here we are using,
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.
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,
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.
I'm pursuing B.Tech in Computer Science from Pune Institute of Computer Technology. I'm avid learner and enthusiastic programmer.