Lexicographically Ordering of Strings in Java

Lexicographic order is the way a dictionary arranges words: compare the first letters, and only if they match, move on to the second letter, and so on. Java gives you this for free through String.compareTo(), but the method has a few rules that surprise people. Uppercase letters sort before lowercase ones, "10" sorts before "9", and a shorter word that is a prefix of a longer one always comes first.

This post explains exactly how compareTo() decides, shows the numbers it actually returns, and then uses it to solve a common practice problem: finding the smallest and largest string in a list. Every snippet below was compiled and run on Java 21.

How compareTo() decides the order

a.compareTo(b) returns an int. You should only care about its sign:

• negative means a comes before b
• zero means the two strings are equal
• positive means a comes after b

Internally, Java walks both strings from the left and stops at the first position where the characters differ. It returns the difference between those two character codes (their UTF-16 values). If one string runs out before any difference is found, the result is the difference in lengths instead. That second rule is why "ab" comes before "abc".

Here is what that looks like in practice:

public class CompareDemo {
    public static void main(String[] args) {
        System.out.println("apple".compareTo("banana"));   // a(97) - b(98)
        System.out.println("cat".compareTo("car"));        // t(116) - r(114)
        System.out.println("ab".compareTo("abc"));         // prefix: 2 - 3
        System.out.println("java".compareTo("java"));
        System.out.println("Zebra".compareTo("apple"));    // Z(90) - a(97)
        System.out.println("Zebra".compareToIgnoreCase("apple"));
        System.out.println("10".compareTo("9"));           // '1' - '9'
    }
}

-1
2
-1
0
-7
25
-8

A few things to notice from those numbers. "cat" vs "car" gives 2 because 't' (116) minus 'r' (114) is 2. "ab" vs "abc" never finds a differing character, so Java returns the length difference, 2 minus 3, which is -1. "Zebra" vs "apple" is negative because capital 'Z' is 90 and small 'a' is 97, so every uppercase letter sorts before every lowercase letter. With compareToIgnoreCase both are treated as lowercase and the result becomes 25. Finally, "10" comes before "9" because the comparison looks at characters, not at numeric value.

Sorting a list of strings

You rarely call compareTo by hand when sorting. Arrays.sort and Collections.sort already use it, and you can pass a Comparator when you want a different order.

import java.util.Arrays;
import java.util.Comparator;

public class SortDemo {
    public static void main(String[] args) {
        String[] words = {"mango", "Apple", "banana", "apple", "Banana"};

        String[] natural = words.clone();
        Arrays.sort(natural);                                  // uses compareTo
        System.out.println(Arrays.toString(natural));

        String[] ignoreCase = words.clone();
        Arrays.sort(ignoreCase, String.CASE_INSENSITIVE_ORDER);
        System.out.println(Arrays.toString(ignoreCase));

        String[] reversed = words.clone();
        Arrays.sort(reversed, Comparator.reverseOrder());
        System.out.println(Arrays.toString(reversed));
    }
}

[Apple, Banana, apple, banana, mango]
[Apple, apple, banana, Banana, mango]
[mango, banana, apple, Banana, Apple]

The first line shows the uppercase-first rule again. In the second line, "Apple" and "apple" are equal when case is ignored, so they keep their original relative order. That happens because sorting objects in Java is stable, which is worth remembering for interview questions.

Practice problem: smallest and largest string

A classic exercise built on this: you get T test cases. Each one gives a number N and then N words made of lowercase English letters. Print the lexicographically smallest word and the largest word, separated by a space. Limits are small: T and N are at most 100, and each word has 1 to 40 letters.

Input
3
3
a ab abc
3
a a b
3
z xy t

Output
a abc
a b
t z

Sorting would work, but it is more than you need. A single pass is enough. Treat the first word as both the current minimum and the current maximum. For every later word, replace the minimum if the word compares smaller, and replace the maximum if it compares larger. That is O(N) comparisons instead of O(N log N).

Dry run on "z xy t": start with min = max = "z". "xy" is smaller than "z", so min becomes "xy". "t" is smaller than "xy" ('t' comes before 'x'), so min becomes "t". Nothing beat "z", so the answer is "t z".

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder out = new StringBuilder();
        while (t-- > 0) {
            int n = sc.nextInt();
            String smallest = sc.next();   // first string is both min and max so far
            String largest = smallest;
            for (int i = 1; i < n; i++) {
                String s = sc.next();
                if (s.compareTo(smallest) < 0) smallest = s;
                if (s.compareTo(largest) > 0) largest = s;
            }
            out.append(smallest).append(' ').append(largest).append('\n');
        }
        System.out.print(out);
    }
}

a abc
a b
t z

I also tried two edge cases. With a single word "hello", the program prints "hello hello", which is correct since that one word is both smallest and largest. With "bb b ba a", it prints "a bb": "b" is a prefix of both "ba" and "bb", so it comes before them, and "bb" beats "ba" on the second letter.

The older version of this code worked, but it started its loop from index 0 and compared the first word with itself. That is harmless, just one wasted comparison. Reading the words directly, without storing them in an array, also keeps memory to O(1).

Common mistakes

• Using == or < on strings. < does not compile for strings, and == compares references, not content. Use equals for equality and compareTo for order.
• Checking for -1 or 1. compareTo can return any negative or positive number, such as -7 or 25. Always test with < 0 or > 0.
• Forgetting about case. If input can mix cases and you want dictionary order, use compareToIgnoreCase or String.CASE_INSENSITIVE_ORDER.
• Sorting numbers stored as strings. "100" sorts before "20". Convert to int or long first, or compare by length and then by text.

Interview questions on this

• What does "apple".compareTo("app") return? 2, because "app" is a prefix and the lengths differ by 2.
• Is compareTo consistent with equals for String? Yes. It returns 0 exactly when equals returns true.
• How would you sort strings by length, then alphabetically? Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()).

Related: Java Substring Comparisons applies the same idea to every substring of a fixed length.

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 Java solutions All coding problems MCQ practice