# [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,

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}")
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,

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;
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:

`acktac`

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.