Java Substring Comparisons | HackerRank Solution

Java Substring Comparisons is a HackerRank warm-up that combines two everyday string skills: taking substrings and comparing strings in dictionary order. You look at every piece of length k in a word and report the smallest and the largest one. It is a sliding-window problem in its simplest form.

The part that catches people is the ordering itself. Java compares strings by character codes, so every capital letter comes before every small letter. "Zoo" is smaller than "ball". Once you understand compareTo, this problem and a lot of sorting questions become easy.

Problem

Strings are ordered lexicographically, which means like a dictionary but with all uppercase letters placed before all lowercase letters: A < B < ... < Z < a < b < ... < z. So ball < cat, dog < dorm, Happy < happy and Zoo < ball.

A substring is a block of consecutive characters. Given a string s and an integer k, find the lexicographically smallest and the lexicographically largest substrings of s that have length exactly k. Complete getSmallestAndLargest(s, k) so it returns them as one string with a newline between them.

Input: the first line is s, the second line is k.

Output: the smallest substring, a newline, then the largest substring.

Constraints: 1 ≤ |s| ≤ 1000, and s contains only English letters (a to z, A to Z). k is at most the length of s.

Input:
welcometojava
3

Output:
ava
wel

The length-3 substrings of "welcometojava" in sorted order are ava, com, elc, eto, jav, lco, met, oja, ome, toj and wel, so the first is "ava" and the last is "wel".

Approach

There are exactly n - k + 1 substrings of length k, one starting at each index from 0 to n - k. You do not need to store or sort them. You only need to remember the best two seen so far.

1. Set both smallest and largest to the first window, s.substring(0, k).
2. For each start i from 1 while i + k <= n, take current = s.substring(i, i + k). Remember that the end index is exclusive.
3. If current.compareTo(smallest) < 0, current comes first in dictionary order, so it becomes the new smallest.
4. If current.compareTo(largest) > 0, it becomes the new largest.
5. Return smallest + "\n" + largest.

How compareTo works. It walks both strings from the start and stops at the first position where the characters differ, then returns the difference of those character codes. 'Z' is 90 and 'a' is 97, which is why uppercase always wins. If one string is a prefix of the other, the shorter one is smaller. A negative result means "this comes first".

Dry run for the first few windows of "welcometojava" with k = 3: start with "wel" for both. "elc" is smaller than "wel" ('e' < 'w'), so smallest becomes "elc". "lco", "com" ('c' < 'e', new smallest), "ome", "met", "eto", "toj", "oja", "jav" follow, and none beats "wel" for largest. Finally "ava" has 'a' at the front, which beats "com", so smallest ends as "ava".

Solution in Java

import java.util.Scanner;

public class Solution {

    public static String getSmallestAndLargest(String s, int k) {
        // Start both answers with the first window
        String smallest = s.substring(0, k);
        String largest = smallest;

        // Slide the window one step at a time: start positions 1 .. n-k
        for (int i = 1; i + k <= s.length(); i++) {
            String current = s.substring(i, i + k);
            if (current.compareTo(smallest) < 0) {
                smallest = current;
            }
            if (current.compareTo(largest) > 0) {
                largest = current;
            }
        }
        return smallest + "\n" + largest;
    }

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

The old solution on this page kept one window and updated it with currstr.substring(1, k) + s.charAt(i), dropping the first character and adding the next. It works, but it builds two new strings per step and is harder to read. Taking s.substring(i, i + k) directly says exactly what you mean.

Tests I ran:

• The sample gives ava and wel.
• aAbB with k = 1 gives A and b. The capitals A and B are smaller than a and b, and b is the biggest letter here.
• Java with k = 4 gives Java twice. When k equals the length there is only one window, and the loop body never runs.
• ZooBall with k = 3 gives Bal and ooB. "Bal" starts with a capital B (66), which beats "Zoo" starting with Z (90).

Output

ava
wel

Complexity

Time: O((n - k + 1) × k). Each of the n - k + 1 windows costs O(k) to create and compare. With n up to 1000 this is at most about a quarter of a million character operations.

Space: O(k) for the current window and the two answers.

Common mistakes

• Looping i < s.length() - k instead of i + k <= s.length(). That skips the very last window, which is "ava" in the sample.
• Comparing strings with < or ==. Java does not allow < on Strings, and == checks if two references are the same object, not the text.
• Using compareToIgnoreCase or lowercasing first. The problem wants the case-sensitive order where capitals come first.
• Collecting every substring into a list and sorting it. It gives the right answer but takes more time and memory for no benefit.

Next in the series: Java Date and Time. For loop practice before this one, see Java Loops II.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice