Lexicographical Smallest & Largest Substring of a given Length in JAVA

By Priyam Sur

Before we understand lexicographically ordered substring in Java, we must understand their definitions. In this Java post, we will learn all about these.

Lexicographically Ordered Substring

Lexicographical Order, also called alphabetic order or dictionary order, orders characters as follows: e.g., cat < dog, House < house, Zebra < bird, umbrella < violet, yellow > Yellow etc.



The substring of a string is a contiguous block of characters in the string: e.g., the substrings of abc are a, b, c, ab, bc and abc. Another example let’s suppose: abcd, where the substrings are a, b, c, d, ab, bc, cd, abc, bcd, abcd.

lexicography

On, the basis of this definitions, let’s suppose a string s, and an integer k are passed as input.

We will create a function so that it finds the lexicographically smallest and largest substrings of length.

The Format of Input:

  • First line input: a string s.
  • Second line input: an integer denoting k.

The Format of Output:

  • The respective lexicographically the smallest and the largest substrings of the string s as a single newline-separated string.

Now, let’s take a look at the code:

//JAVA8

import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.io.InputStream;
import java.io.InputStreamReader;
public class Solution {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solution(1, in, out);
    out.close();
  }
}

class Task {
    public void solution(int testNumber, InputReader in, PrintWriter out) {
        String str = in.next();
        int k = in.nextInt();

        String min = null, max = null;

        for (int i=0; i<=str.length()-k; i++){
            String sub = str.substring(i, i+k);
            if (min == null || min.compareTo(sub) > 0){
                min = sub;
            }
            if (max == null || max.compareTo(sub) < 0){
                max = sub;
            }
        }
        out.println(min);
        out.println(max);
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}

 

Input:

welcometojava
3

Explanation:

String s=”welcometojava” has the following lexicographically-ordered substrings of length k=3:

["ava", "com", "elc", "eto", "jav", "lco", "met", "oja", "ome", "toj", "wel"]

So, in the output, we must return the first (lexicographically smallest) substring and the last (lexicographically largest) substring as two newline-separated values (i.e., ava \n wel) according to the output format.

Output:

ava
wel

Also Read:

Leave a Reply

Your email address will not be published. Required fields are marked *