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