(Java) alphabetic substring comparison ends up with a wrong result

Question

In one of these HackerRank Java challenges, there is a problem which is defined as:

The problem

We define the following terms:

• Lexicographical Order, also known as alphabetic or dictionary order, orders characters as follows: A < B < ...< Y < Z < a < b ... < y < z

• A substring of a string is a contiguous block of characters in the string. For example, the substrings of abc are a, b, c, ab, bc, and abc.

Given a string, s, and an integer, k, complete the function so that it finds the lexicographically smallest and largest substrings of length k.

Here is my (not fully working) solution:

My code

import java.util.*;

public class stringCompare {

    public static String getSmallestAndLargest(String s, int k) {
        String smallest, largest, temp;

        /* Initially, define the smallest and largest substrings as the first k chars */
        smallest = s.substring(0, k);
        largest = s.substring(0, k);

        for (int i = 0; i <= s.length() - k; i++) {
            temp = s.substring(i, i + k);
            for (int j = 0; j < k; j++) {

                /* Check if the first char of the next substring is greater than the largest ones' */
                if (temp.charAt(j) > largest.charAt(j)) {
                    largest = s.substring(i, i + k);
                    break;      
                }

                /* Check if the first char of the next substring is less than the smallest ones' */
                else if (temp.charAt(j) < smallest.charAt(j)) {
                    smallest = s.substring(i, i + k);
                    break;
                } 

                /* Check if the first char of the next substring is either equal to smallest or largest substrings' */
                else if (temp.charAt(j) == smallest.charAt(j)
                        || temp.charAt(j) == largest.charAt(j)) {
                    // If so, move to the next char till it becomes different
                } 

                /* If the first of char of the next substring is neither of these (between smallest and largest ones')
                    skip that substring */ 
                else {
                    break;
                }
            }
        }

        return smallest + "\n" + largest;
    }

    public static void main(String[] args) {
        String s;
        int k;
        try (Scanner scan = new Scanner(System.in)) {
            s = scan.next();
            k = scan.nextInt();
        }

        System.out.println(getSmallestAndLargest(s, k));
    }
}

According to the HackerRank, this code fails for 2 out of 6 cases. One is as follows:

ASDFHDSFHsdlfhsdlfLDFHSDLFHsdlfhsdlhkfsdlfLHDFLSDKFHsdfhsdlkfhsdlfhsLFDLSFHSDLFHsdkfhsdkfhsdkfhsdfhsdfjeaDFHSDLFHDFlajfsdlfhsdlfhDSLFHSDLFHdlfhs
30

The expected output is:

ASDFHDSFHsdlfhsdlfLDFHSDLFHsdl
sdlkfhsdlfhsLFDLSFHSDLFHsdkfhs

But mine becomes:

DFHSDLFHDFlajfsdlfhsdlfhDSLFHS
sdlkfhsdlfhsLFDLSFHSDLFHsdkfhs

At debug mode, I found that the smallest substring was correct until the 67th iteration (i). I don't know why it changes to a wrong one at that step but it does.

Can anyone help me on that, please?

Thanks!

Answer 1

The problem is that you are trying your comparison for both largest and smallest in a single loop. More specifically, this line is problematic:

else if (temp.charAt(j) == smallest.charAt(j)
      || temp.charAt(j) == largest.charAt(j)) {
    // If so, move to the next char till it becomes different
}

You may want to continue the loop on j to detect the smallest substring, but break out of the loop on j to detect the largest substring. That's why the two checks should be done independently of each other.

A few minor points to consider:

• You do not need to write largest = s.substring(i, i + k), because it is the same as largest = temp; same goes for smallest.
• You do not need the nested loop at all compareTo performs lexicographic comparison for you.

Essentially, your program could be reduced to this:

largest = smallest = s.substring(0, k);
for (int i = 1 ; i <= s.length() - k; i++) {
    temp = s.substring(i, i + k);
    if (temp.compareTo(largest) > 0) {
        largestt = temp;
    } else if (temp.compareTo(smallest) < 0) {
        smalles = temp;
    }
}

Note that the loop can start from i = 1 because you used s.substring(0, k) to initialize both largest and smallest.

Answer 2

You cannot compare a certain substring to both the smallest so far and the largest so far at the same time. Especially the condition

temp.charAt(j) == smallest.charAt(j)
                    || temp.charAt(j) == largest.charAt(j)

is problematic. Take for example

smallest   ad
largest    bx
temp       bc

In this example your code will conclude that bc is smaller than ad

Answer 3

I propose a simple optimisation: a quick peek at the first characters.

largest = smallest = s.substring(0, k);
for (int i = 1; i <= s.length() - k; i++) {
    if (s.charAt(i) > largest.charAt(0) ){
      largest = s.substring(i, i + k);
      continue;
    }
    if (s.charAt(i) < smallest.charAt(0) ){
      smallest = s.substring(i, i + k);
      continue;
    }

    if (s.charAt(i) == largest.charAt(0) ){
        String temp = s.substring(i, i + k);
        if( temp.compareTo(largest) > 0) {
            largest = temp;
            continue;
        }
    }
    if (s.charAt(i) == smallest.charAt(0) ){
        String temp = s.substring(i, i + k);
        if( temp.compareTo(smallest) < 0) {
            smallest = temp;
        }
    }
}

For the example, comparisons drop from 222 to 14.