Sorting a String in lexicographical order

Question

The question provides an input String and an integer, it asks us to convert the string into all the possible combinations of sub-strings of length as specified by the input integer provided. Then we have to find the maximum and minimum from those sub-strings.

I found a solution for the problem but can anyone please explain the looping part. The Solution:

import java.io.*;`
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int k = sc.nextInt();
        String maxString = s.substring(0, k);
        String minString = s.substring(0, k);

        for (int i = 1; i <= s.length() - k; ++i){
            if (maxString.compareTo(s.substring(i, i + k)) < 0)
                maxString = s.substring(i, i + k);
            if (minString.compareTo(s.substring(i, i + k)) > 0)
                minString = s.substring(i, i + k);
        }

        System.out.println(minString);
        System.out.println(maxString);
    }
}

for the sake of readability and performance: `S.substring(i,i+k)` should be only executed once and then saved — Lino, Jul 23 '18 at 14:26
@Lino there is no such need, since `substring` will only cause little overhead. Refer to: https://stackoverflow.com/questions/10830004/what-does-string-substring-exactly-do-in-java and https://stackoverflow.com/questions/20260140/how-to-detect-whether-string-substring-copies-the-character-data — Hearen, Jul 23 '18 at 14:32
@Hearen but why pay the overhead, however little it may be, when there is almost no benefit? — jingx, Jul 23 '18 at 15:08
@jingx personal style is also beneficial. of course for me I will not do that, but it's not that serious here. — Hearen, Jul 23 '18 at 15:15

score 0 · Accepted Answer · edited Jun 20 '20 at 09:12

These two substring will be the start

String maxString = S.substring(0, k); // start from index 0

String minString = S.substring(0, k);

in the loop for (int i=1;i<=S.length()-k;++i), we start from index=1 till the last possible index S.length()-k which still can give us a substring with length k.

We loop through from the index 0 (the initialisation part) till the last index S.length() - k (in the loop, the last iteration):

if the substring is bigger we do the updating maxString = S.substring(i,i+k);
if smaller than minString, we do the updating minString = S.substring(i,i+k);

Also as Lino and jingx mentioned, I refactored your code as follows:

public static void main(String... args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int k = sc.nextInt();
    String maxString = s.substring(0, k);
    String minString = s.substring(0, k);

    for (int i = 1; i <= s.length() - k; ++i){
        String curSubstr = s.substring(i, i + k);
        System.out.println(curSubstr);
        if (maxString.compareTo(curSubstr) < 0)
            maxString = s.substring(i, i + k);
        if (minString.compareTo(curSubstr) > 0)
            minString = s.substring(i, i + k);
    }

    System.out.println(minString);
    System.out.println(maxString);
}

Have a local test as follows:

Case #1
Input: 
HelloWorld 
2
Output:
el
ll
lo
oW
Wo
or
rl
ld
He // the min
rl // the max

thanks for the answer. But can we also use S.length() in the loop instead of S.length()-k ? — jishnu bhattacharyya, Jul 23 '18 at 15:10
Not really, as I mentioned it will ensure `the last iteration` is correct (not out of bound) — Hearen, Jul 23 '18 at 15:13
It gives error: Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 11 at java.lang.String.substring(Unknown Source). — jishnu bhattacharyya, Jul 23 '18 at 15:30
You have to provide a case for me to re-produce the error. It's correct, the code itself. — Hearen, Jul 23 '18 at 15:40

Sorting a String in lexicographical order

1 Answers1