[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.