9.06Beginner / Intermediate6 topics16 min6 interactive animations

Lexicographic reasoning

Lexicographic order is dictionary order on code units. This lesson covers natural order, compareTo, sorting characters by counting, custom alphabets, the next permutation algorithm and prefix relationships such as the longest common prefix.

Learning goals

Predict compareTo results
Sort characters in O(n + alphabet)
Implement a custom order
Generate the next permutation in place

Prerequisites

Core operationsCharacter patterns

9.06.1

Natural order

Lexicographic (dictionary) order compares strings character by character; the first difference decides, and a proper prefix comes before the longer string. In Java the comparison is by UTF-16 code unit, so uppercase letters sort before lowercase ('Z' < 'a') and accented letters come after 'z'. String.CASE_INSENSITIVE_ORDER and Collator give friendlier orders.

Compare two strings step by step in the animation.

Java

1List<String> w = new ArrayList<>(List.of("banana", "Apple", "cherry", "apple"));
2Collections.sort(w);                                    // [Apple, apple, banana, cherry]: 'A' (65) < 'a' (97)
3w.sort(String.CASE_INSENSITIVE_ORDER);                  // [Apple, apple, banana, cherry] (stable)

compareTo and common prefix

Interactive · edit the input

char[] a · length 5

01234

ComparingEqual so farFirst difference

Setup

Compare character by character over the shorter length (5); the first difference decides.

Step 1 / 5

Java

1static int compareTo(String a, String b) {
2    int lim = Math.min(a.length(), b.length());
3    for (int k = 0; k < lim; k++) {
4        char x = a.charAt(k), y = b.charAt(k);
5        if (x != y) return x - y;                    // difference of the two code units
6    }
7    return a.length() - b.length();                  // one string is a prefix of the other
8}
9static int commonPrefix(String a, String b) {
10    int k = 0;
11    while (k < a.length() && k < b.length() && a.charAt(k) == b.charAt(k)) k++;
12    return k;
13}

Live state

a.length()

b.length()

lim

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2	a.length()=5 b.length()=7 lim=5	Compare character by character over the shorter length (5); the first difference decides.
2	L5	k=0 x='a' (97) y='a' (97)	'a' equals 'a'.
3	L5	k=1 x='p' (112) y='p' (112)	'p' equals 'p'.
4	L5	k=2 x='p' (112) y='r' (114)	'p' (112) differs from 'r' (114).
5	L5	return=-2	Return 112 - 114 = -2: a sorts before b. Only the sign is guaranteed; do not rely on the magnitude.

9.06.2

CompareTo

a.compareTo(b) returns the difference of the first differing code units, or the length difference when one string is a prefix of the other, and 0 when they are equal. Only the sign is part of the contract: negative means a sorts first, positive means after. Use it as a comparator and never rely on the exact value.

Try the equal and prefix presets.

Java

1int a = "apple".compareTo("apricot");      // -2: 'p' (112) - 'r' (114)
2int b = "java".compareTo("javascript");    // -6: length difference 4 - 10
3int c = "same".compareTo("same");          // 0
4Comparator<String> byLength = Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder());

compareTo and common prefix

Interactive · edit the input

char[] a · length 5

01234

ComparingEqual so farFirst difference

Setup

Compare character by character over the shorter length (5); the first difference decides.

Step 1 / 5

Java

1static int compareTo(String a, String b) {
2    int lim = Math.min(a.length(), b.length());
3    for (int k = 0; k < lim; k++) {
4        char x = a.charAt(k), y = b.charAt(k);
5        if (x != y) return x - y;                    // difference of the two code units
6    }
7    return a.length() - b.length();                  // one string is a prefix of the other
8}
9static int commonPrefix(String a, String b) {
10    int k = 0;
11    while (k < a.length() && k < b.length() && a.charAt(k) == b.charAt(k)) k++;
12    return k;
13}

Live state

a.length()

b.length()

lim

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2	a.length()=5 b.length()=7 lim=5	Compare character by character over the shorter length (5); the first difference decides.
2	L5	k=0 x='a' (97) y='a' (97)	'a' equals 'a'.
3	L5	k=1 x='p' (112) y='p' (112)	'p' equals 'p'.
4	L5	k=2 x='p' (112) y='r' (114)	'p' (112) differs from 'r' (114).
5	L5	return=-2	Return 112 - 114 = -2: a sorts before b. Only the sign is guaranteed; do not rely on the magnitude.

9.06.3

Sort characters

Sorting the characters of a string with a comparison sort costs O(n log n). With a small alphabet, counting sort is O(n + 26): count each letter, then write each letter as many times as it occurred. In Java char[] cs = s.toCharArray(); Arrays.sort(cs); is the short form.

Use natural order in the animation; the output is the sorted string.

Java

1static String sortChars(String s) {
2    int[] count = new int[26];
3    for (char c : s.toCharArray()) count[c - 'a']++;
4    StringBuilder out = new StringBuilder();
5    for (int i = 0; i < 26; i++) out.append(String.valueOf((char) ('a' + i)).repeat(count[i]));
6    return out.toString();
7}

Sorting characters by counting (natural or custom order)

Interactive · edit the input

char[] s · length 7

0123456

CountingBeing written to the outputSorted

count[c]

empty

out

empty

Setup

Count each letter first, then write the letters in the order "cba". No comparisons are needed: O(n + 26).

Step 1 / 13

Java

1static String sortChars(String s, String order) {        // order = "abc...z" for natural order
2    int[] count = new int[26];
3    for (char c : s.toCharArray()) count[c - 'a']++;
4    StringBuilder out = new StringBuilder();
5    for (char c : order.toCharArray()) {
6        out.append(String.valueOf(c).repeat(count[c - 'a']));
7        count[c - 'a'] = 0;
8    }
9    for (char c = 'a'; c <= 'z'; c++) out.append(String.valueOf(c).repeat(count[c - 'a']));   // leftovers, natural order
10    return out.toString();
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2		Count each letter first, then write the letters in the order "cba". No comparisons are needed: O(n + 26).
2	L3	i=0 c='c' count=1	count['c'] = 1.
3	L3	i=1 c='b' count=1	count['b'] = 1.
4	L3	i=2 c='a' count=1	count['a'] = 1.
5	L3	i=3 c='d' count=1	count['d'] = 1.
6	L3	i=4 c='c' count=2	count['c'] = 2.
7	L3	i=5 c='a' count=2	count['a'] = 2.
8	L3	i=6 c='b' count=2	count['b'] = 2.
9	L6	c='c' repeat=2	Next in the order: write 'c' 2 times.
10	L6	c='b' repeat=2	Next in the order: write 'b' 2 times.
11	L6	c='a' repeat=2	Next in the order: write 'a' 2 times.
12	L9	c='d' repeat=1	Not in the order, so appended naturally: write 'd' 1 time.
13	L10	return="ccbbaad"	Result "ccbbaad". Counting beats O(n log n) comparison sorting when the alphabet is small.

9.06.4

Custom ordering

A custom order is an alphabet permutation given as a string: letters appear in the result according to their position in it. Count the input letters, write them in the order of the custom alphabet (zeroing each count), then append any remaining letters. A comparator can express the same rule with a rank array: rank[c - 'a'].

Try the order “cba” and a letter that is missing from the order.

Java

1static String customSort(String s, String order) {
2    int[] count = new int[26];
3    for (char c : s.toCharArray()) count[c - 'a']++;
4    StringBuilder out = new StringBuilder();
5    for (char c : order.toCharArray()) { out.append(String.valueOf(c).repeat(count[c - 'a'])); count[c - 'a'] = 0; }
6    for (char c = 'a'; c <= 'z'; c++) out.append(String.valueOf(c).repeat(count[c - 'a']));
7    return out.toString();
8}

Sorting characters by counting (natural or custom order)

Interactive · edit the input

char[] s · length 7

0123456

CountingBeing written to the outputSorted

count[c]

empty

out

empty

Setup

Count each letter first, then write the letters in the order "cba". No comparisons are needed: O(n + 26).

Step 1 / 13

Java

1static String sortChars(String s, String order) {        // order = "abc...z" for natural order
2    int[] count = new int[26];
3    for (char c : s.toCharArray()) count[c - 'a']++;
4    StringBuilder out = new StringBuilder();
5    for (char c : order.toCharArray()) {
6        out.append(String.valueOf(c).repeat(count[c - 'a']));
7        count[c - 'a'] = 0;
8    }
9    for (char c = 'a'; c <= 'z'; c++) out.append(String.valueOf(c).repeat(count[c - 'a']));   // leftovers, natural order
10    return out.toString();
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2		Count each letter first, then write the letters in the order "cba". No comparisons are needed: O(n + 26).
2	L3	i=0 c='c' count=1	count['c'] = 1.
3	L3	i=1 c='b' count=1	count['b'] = 1.
4	L3	i=2 c='a' count=1	count['a'] = 1.
5	L3	i=3 c='d' count=1	count['d'] = 1.
6	L3	i=4 c='c' count=2	count['c'] = 2.
7	L3	i=5 c='a' count=2	count['a'] = 2.
8	L3	i=6 c='b' count=2	count['b'] = 2.
9	L6	c='c' repeat=2	Next in the order: write 'c' 2 times.
10	L6	c='b' repeat=2	Next in the order: write 'b' 2 times.
11	L6	c='a' repeat=2	Next in the order: write 'a' 2 times.
12	L9	c='d' repeat=1	Not in the order, so appended naturally: write 'd' 1 time.
13	L10	return="ccbbaad"	Result "ccbbaad". Counting beats O(n log n) comparison sorting when the alphabet is small.

9.06.5

Next permutation

The next lexicographic permutation: scan from the right for the first position i where a[i] < a[i + 1] (the pivot); swap it with the smallest suffix value that is larger; then reverse the suffix to make it as small as possible. If no pivot exists the string is the last permutation and reversing it gives the first. O(n) time, O(1) space, and duplicates are handled naturally.

Try “dcba” (the last permutation) and “aabb”.

Java

1static boolean nextPermutation(char[] a) {
2    int i = a.length - 2;
3    while (i >= 0 && a[i] >= a[i + 1]) i--;
4    if (i >= 0) {
5        int j = a.length - 1;
6        while (a[j] <= a[i]) j--;
7        char t = a[i]; a[i] = a[j]; a[j] = t;
8    }
9    for (int lo = i + 1, hi = a.length - 1; lo < hi; lo++, hi--) { char t = a[lo]; a[lo] = a[hi]; a[hi] = t; }
10    return i >= 0;
11}

Next lexicographic permutation

Interactive · edit the input

char[] a · length 4

0123

ScanningPivot (rightmost ascent)SwappedReversed suffix

Setup

The next permutation keeps the longest possible prefix. Scan from the right for the first place where the order goes up.

Step 1 / 7

Java

1static boolean nextPermutation(char[] a) {            // false if a was the last permutation
2    int i = a.length - 2;
3    while (i >= 0 && a[i] >= a[i + 1]) i--;            // rightmost ascent a[i] < a[i + 1]
4    if (i >= 0) {
5        int j = a.length - 1;
6        while (a[j] <= a[i]) j--;                      // smallest suffix value bigger than a[i]
7        swap(a, i, j);
8    }
9    reverse(a, i + 1, a.length - 1);                   // the suffix is descending: make it ascending
10    return i >= 0;
11}

Live state

0 swaps

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L2	i=2	The next permutation keeps the longest possible prefix. Scan from the right for the first place where the order goes up.
2	L3	i=2	Not an ascent: the suffix from here is still non-increasing, the largest possible arrangement of those letters.
3	L3	i=1 pivot='c'	Ascent found: the pivot is 'c' at index 1. Everything to its right is non-increasing.
4	L6	i=1 j=3	'b' is not bigger than the pivot: keep looking left.
5	L7	i=1 j=2	Swap the pivot with 'd', the smallest suffix letter that is bigger.
6	L9	lo=2 hi=3	Reverse the suffix: swap positions 2 and 3.
7	L10	return="adbc" wrapped=false	Next permutation: "adbc". The suffix after the pivot is now the smallest arrangement. O(n).

9.06.6

Prefix relationships

Prefix relations drive tries, autocomplete and sorting: a string is a prefix of another if it matches its beginning, and the longest common prefix (LCP) of two strings is the number of leading characters they share. The LCP of a list is the LCP of its smallest and largest strings in sorted order.

Switch the animation to the common-prefix mode.

Java

1static int commonPrefix(String a, String b) {
2    int k = 0;
3    while (k < a.length() && k < b.length() && a.charAt(k) == b.charAt(k)) k++;
4    return k;
5}
6static String lcp(String[] words) {
7    String lo = words[0], hi = words[0];
8    for (String w : words) { if (w.compareTo(lo) < 0) lo = w; if (w.compareTo(hi) > 0) hi = w; }
9    return lo.substring(0, commonPrefix(lo, hi));
10}

compareTo and common prefix

Interactive · edit the input

char[] a · length 5

01234

ComparingEqual so farFirst difference

Setup

Compare character by character over the shorter length (5); the first difference decides.

Step 1 / 5

Java

1static int compareTo(String a, String b) {
2    int lim = Math.min(a.length(), b.length());
3    for (int k = 0; k < lim; k++) {
4        char x = a.charAt(k), y = b.charAt(k);
5        if (x != y) return x - y;                    // difference of the two code units
6    }
7    return a.length() - b.length();                  // one string is a prefix of the other
8}
9static int commonPrefix(String a, String b) {
10    int k = 0;
11    while (k < a.length() && k < b.length() && a.charAt(k) == b.charAt(k)) k++;
12    return k;
13}

Live state

a.length()

b.length()

lim

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2	a.length()=5 b.length()=7 lim=5	Compare character by character over the shorter length (5); the first difference decides.
2	L5	k=0 x='a' (97) y='a' (97)	'a' equals 'a'.
3	L5	k=1 x='p' (112) y='p' (112)	'p' equals 'p'.
4	L5	k=2 x='p' (112) y='r' (114)	'p' (112) differs from 'r' (114).
5	L5	return=-2	Return 112 - 114 = -2: a sorts before b. Only the sign is guaranteed; do not rely on the magnitude.

Practice ladder

Now try it yourself

Easy

Sort the letters of "banana"
Which is smaller: "Zebra" or "apple"? Why?

Medium

Sort “cbadcab” by the custom order “cba”
Compute the next permutation of 1243 and 4321

Advanced

Generate all permutations of a string with duplicates in lexicographic order using next permutation

Key takeaways

Lexicographic order compares code units; the first difference or the length decides.
Counting sort orders letters in O(n + 26) and supports custom alphabets.
Next permutation: rightmost ascent, swap with the next larger suffix value, reverse the suffix.