Problem 158: Exploring Strings for Which Only One Character Comes Lexicographically After Its Neighbour

Project Euler Problem 158 Solution

EulerSolve provides an optimized solution for Project Euler Problem 158, Exploring Strings for Which Only One Character Comes Lexicographically After Its Neighbour, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $p(n)$ be the number of length-$n$ strings formed from an ordered alphabet of size $26$, with no repeated letters, such that there is exactly one index $i$ for which the next character is larger: $s_i \lt s_{i+1}$. The task is to determine $$\max_{1 \le n \le 26} p(n).$$ The implementations use a closed counting formula rather than generating strings. For the standard $26$-letter alphabet, the maximum occurs at $n=18$ and equals $409511334375$. Mathematical Approach The problem separates naturally into two pieces: choose which letters appear, then count how many relative orders of those letters contain exactly one ascent. Relabel the chosen letters without changing the condition Suppose we choose any $n$ distinct letters from the alphabet and list them in increasing order as $L_1 \lt L_2 \lt \cdots \lt L_n$. Replacing $L_j$ by $j$ preserves every comparison between adjacent characters, so the actual letter names are irrelevant once the set of letters is fixed. Therefore, if $a(n)$ denotes the number of permutations $\pi_1\pi_2\cdots\pi_n$ of $\{1,2,\dots,n\}$ with exactly one ascent, then $$p(n)=\binom{26}{n}a(n).$$ The entire problem is now reduced to finding $a(n)$....

Detailed mathematical approach

Problem Summary

We form strings from $n$ different letters of the $26$-letter alphabet, $1\le n\le26$, and look at the letters that come later in the alphabet than their neighbour to the left; for single letters, lexicographic order is simply alphabetical order. ^[2] In $\mathtt{abc}$ two letters do so, in $\mathtt{hat}$ exactly one, the $\mathtt t$ after the $\mathtt a$, and in $\mathtt{zyx}$ none. Let $p(n)$ be the number of strings of $n$ different letters in which exactly one letter comes later in the alphabet than its left neighbour. The statement gives $p(3)=10400$, and we must find the largest of the values $p(1),p(2),\dots,p(26)$. ^[1]

The whole solution in one sentence: a string with exactly one such letter is a run of letters going backwards through the alphabet followed by a second such run, so it is fixed by choosing its $n$ letters and the letters of its first run, which gives $p(n)=\binom{26}{n}(2^n-n-1)$, and the programs evaluate this formula for all $26$ lengths and keep the largest value.

Mathematical Approach

1. Ascents in tiny strings

Write a string as $s_1s_2\cdots s_n$. A position $i$ with $1\le i\le n-1$ and $s_i\lt s_{i+1}$, meaning that $s_{i+1}$ comes later in the alphabet, is called an ascent, and a position with $s_i\gt s_{i+1}$ a descent; these are the standard names from the study of permutations. ^[5] Every letter that comes after its left neighbour marks one ascent, so $p(n)$ counts the strings with exactly one ascent. Since the letters are different, each of the $n-1$ neighbouring pairs is either an ascent or a descent.

$n=1$: there is no neighbouring pair and so no ascent, hence $p(1)=0$.
$n=2$: two letters $x\lt y$ give the string $xy$, with one ascent, and $yx$, with none. Every pair of letters contributes exactly one good string, so $p(2)=\binom{26}{2}=325$.
$n=3$: the letters $\mathtt a$, $\mathtt h$, $\mathtt t$ can be arranged in six orders. $\mathtt{aht}$ has two ascents; $\mathtt{ath}$, $\mathtt{hat}$, $\mathtt{hta}$ and $\mathtt{tah}$ have one; $\mathtt{tha}$ has none. Only the alphabetical order of the three letters matters here, so every set of three letters gives exactly $4$ good strings. There are $\binom{26}{3}=2600$ such sets, and $p(3)=2600\cdot4=10400$, the value of the statement.

2. Only the order of the letters matters

Fix a set of $n$ letters and list them alphabetically as $L_1\lt L_2\lt\dots\lt L_n$. Replacing every $L_j$ by the number $j$ turns a string of these letters into an arrangement of the numbers $1,2,\dots,n$, a permutation, and it keeps every comparison between neighbours, so the ascents stay where they are. For example, with $\mathtt a\to1$, $\mathtt h\to2$ and $\mathtt t\to3$, the string $\mathtt{hat}$ becomes $213$, with its single ascent at position $2$. Let $a(n)$ be the number of permutations of $1,\dots,n$ with exactly one ascent. A string of different letters is the same as a choice of its set of letters together with a permutation, and there are $\binom{26}{n}$ sets of $n$ letters, ^[3] so by the rule of product ^[4]

$$p(n)=\binom{26}{n}\,a(n).$$

For an alphabet of $m$ letters the same argument gives $p_m(n)=\binom mn\,a(n)$, so $p=p_{26}$, and the hard part, $a(n)$, no longer depends on the alphabet. Section 1 gives $a(1)=0$, $a(2)=1$ and $a(3)=4$.

3. Two descending runs

Writing out all $24$ permutations of $1,2,3,4$ shows that exactly $11$ of them have one ascent:

$1432,\ 2143,\ 2431,\ 3142,$
$3214,\ 3241,\ 3421,\ 4132,$
$4213,\ 4231,\ 4312.$

Look at $3142$: it descends from $3$ to $1$, ascends to $4$ and descends again to $2$. The same happens in general. If the only ascent of a permutation $\pi_1\pi_2\cdots\pi_n$ is at position $k$, every other neighbouring pair is a descent, so

$$\pi_1\gt\pi_2\gt\dots\gt\pi_k\lt\pi_{k+1}\gt\dots\gt\pi_n.$$

The permutation consists of two descending runs, and it is completely determined by the set $S=\{\pi_1,\dots,\pi_k\}$ of its first run: the elements of $S$ come first, in decreasing order, and then the other elements, the complement $T$, also in decreasing order. For $3142$ we have $S=\{1,3\}$ and $T=\{2,4\}$.

4. Counting the first runs

Claim. $a(n)=2^n-n-1$ for every $n\ge1$.

Proof. For a subset $S$ of $\{1,\dots,n\}$, let $\sigma(S)$ be the sequence that lists $S$ in decreasing order followed by its complement $T$ in decreasing order. Inside each part there are only descents, so $\sigma(S)$ has at most one ascent, at the junction, and it has one exactly when both parts are nonempty and $\min S\lt\max T$; call such a set $S$ good. By Section 3 every permutation with one ascent is $\sigma(S)$ for a good $S$, namely the set of its first run. Different good sets give different permutations, because the ascent of $\sigma(S)$ lies between positions $|S|$ and $|S|+1$, so $S$ can be read off from $\sigma(S)$ as the set of its first $|S|$ entries. Hence $a(n)$ is the number of good sets. A set $S$ is not good exactly when every element of $S$ is larger than every element of $T$, the empty set and the whole set included, that is, when $S=\{t+1,t+2,\dots,n\}$ for one of the $n+1$ values $t=0,1,\dots,n$. Of the $2^n$ subsets, $n+1$ are not good, so

$$a(n)=2^n-(n+1)=2^n-n-1.\qquad\square$$

For $n=3$, the eight subsets of $\{1,2,3\}$ include the four sets $\varnothing$, $\{3\}$, $\{2,3\}$ and $\{1,2,3\}$ that are not good; each of them gives the descending sequence $321$. The good sets $\{1\}$, $\{2\}$, $\{1,2\}$ and $\{1,3\}$ give $132$, $231$, $213$ and $312$, which are the four strings $\mathtt{ath}$, $\mathtt{hta}$, $\mathtt{hat}$ and $\mathtt{tah}$ of Section 1 after relabelling. For $n=4$ the formula gives $16-5=11$, the list of Section 3.

5. A second count: inserting the largest number

A second, inductive argument confirms the claim and connects it with the Eulerian numbers. For $n\ge2$, every permutation of $1,\dots,n$ arises exactly once by inserting $n$ into one of the $n$ gaps of a permutation $\tau$ of $1,\dots,n-1$: before the first entry, between two neighbours or after the last entry; removing $n$ again recovers $\tau$ and the gap. Inserting $n$ at the front adds a descent and changes no ascent. Inserting it at the end adds an ascent. Inserting it between $\tau_i$ and $\tau_{i+1}$ replaces that pair by an ascent $\tau_i\lt n$ followed by a descent $n\gt\tau_{i+1}$, so the number of ascents stays the same if $\tau_i\lt\tau_{i+1}$ and grows by one otherwise. Insertion never removes an ascent, so a permutation with exactly one ascent comes either from a $\tau$ with one ascent, with $n$ put at the front or into that ascent, two choices, or from the only $\tau$ without ascents, $n-1,n-2,\dots,1$, with $n$ put into any of its other $n-1$ gaps. Hence

$$a(n)=2\,a(n-1)+(n-1),\qquad a(1)=0,$$

which gives $0,1,4,11,26,57,120,\dots$; and $2^n-n-1$ satisfies it, because $2\bigl(2^{n-1}-n\bigr)+n-1$${}=2^n-n-1$. For $n=3$: from $12$ we get $312$ and $132$, from $21$ we get $231$ and $213$. The numbers $A(n,k)$ of permutations of $1,\dots,n$ with exactly $k$ ascents are the Eulerian numbers, and the same insertion argument, with $k+1$ gaps that keep the count and $n-k$ gaps that raise it from $k-1$ to $k$, gives their recurrence ^[5]

$$A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1).$$

It holds for $n\ge2$, starting from $A(1,0)=1$, with $A(n,k)=0$ for $k\lt0$ or $k\ge n$, and our $a(n)$ is $A(n,1)$. Reading a permutation backwards turns its ascents into descents, so $a(n)$ also counts the permutations with exactly one descent, and this is how the On-Line Encyclopedia of Integer Sequences describes the sequence $2^n-n-1$. ^[6]

6. The formula and a small alphabet

Sections 2 and 4 together give

$$p(n)=\binom{26}{n}\bigl(2^n-n-1\bigr).$$

The first values are $p(1)=0$, $p(2)=325$, $p(3)=10400$, $p(4)=14950\cdot11=164450$ and $p(5)=65780\cdot26=1710280$. Both factors grow up to $n=13$; after that $\binom{26}{n}$ shrinks back to $1$, while $2^n-n-1$ keeps roughly doubling, so the two compete. A small alphabet shows the outcome. With the five letters $\mathtt a$ to $\mathtt e$, the values $p_5(n)=\binom5n(2^n-n-1)$ for $n=1,\dots,5$ are $5\cdot0=0$, $10\cdot1=10$, $10\cdot4=40$, $5\cdot11=55$ and $1\cdot26=26$. The maximum is $55$, at $n=4$; a direct enumeration of all $325$ strings of different letters from $\mathtt a$ to $\mathtt e$ finds the same counts.

7. The values rise to one peak and then fall

For an alphabet of $m$ letters and $2\le n\le m-1$, both $p_m(n)$ and $p_m(n+1)$ are positive, and since $\binom{m}{n+1}=\binom mn\frac{m-n}{n+1}$, their ratio is

$$r_m(n)=\frac{p_m(n+1)}{p_m(n)}=\frac{m-n}{n+1}\,q(n),$$

$$q(n)=\frac{2^{n+1}-n-2}{2^n-n-1}=2+\frac{n}{2^n-n-1}.$$

Claim. $r_m(n)$ strictly decreases as $n$ runs from $2$ to $m-1$.

Proof. The factor $(m-n)/(n+1)$ is positive and strictly decreasing. For $q$, compare $n/(2^n-n-1)$ with $(n+1)/(2^{n+1}-n-2)$. Both denominators are positive for $n\ge2$, so the second fraction is the smaller one exactly when

$$(n+1)\bigl(2^n-n-1\bigr)\lt n\bigl(2^{n+1}-n-2\bigr).$$

Expanding both sides and cancelling $n^2+2n$, this becomes $(1-n)\,2^n\lt1$, which holds for every $n\ge1$. So $q$ is positive and strictly decreasing as well, and so is the product. $\square$

Consequently the values $p_m(2),\dots,p_m(m)$ increase as long as the ratio is above $1$, and once it has dropped to $1$ or below they never increase again. Such a sequence is called unimodal, and its maximum sits at the turning point; $p_m(1)=0$ is smaller than all of them. For five letters the ratios are $r_5(2)=4$, $r_5(3)=11/8$ and $r_5(4)=26/55$, so the values rise twice and then fall, with the peak $55$ found above. A search could therefore stop at the first decrease, but there are only $26$ lengths, and the programs simply evaluate all of them.

8. How large the numbers get

The ratio $(26-n)/(n+1)$ of neighbouring binomial coefficients exceeds $1$ exactly for $n\le12$, so every $\binom{26}{n}$ is at most the middle one, $\binom{26}{13}=10400600$. With $2^n-n-1\lt2^{26}$, every $p(n)$ is therefore below $10400600\cdot2^{26}\approx6.98\cdot10^{14}$, far below $2^{63}\approx9.22\cdot10^{18}$. On the other hand $p(10)=5311735\cdot1013=5380787555$ is already larger than $2^{32}$: $32$-bit integers would overflow, while $64$-bit integers are more than enough.

How the Code Works

The C++ program ^[7] starts in main, which reads two options with parse_arguments: --skip-checkpoints, and --alphabet=K for an alphabet of $K$ letters instead of $26$. An unknown argument, an alphabet value that is empty or contains a non-digit, or a size of $0$ in the last --alphabet= option ends the program with exit code $1$; parse_int_after_prefix collects the digits in an int without a range check, so an oversized value overflows, which is undefined behaviour. Unless switched off, run_checkpoints then requires p_of_n(26, 3) to equal $10400$, the value of the statement, and exits with code $2$ otherwise. Finally main prints solve(alphabet).

solve runs through $n=1,\dots,K$, keeps the largest value of p_of_n(K, n) in best and returns it, without stopping early. p_of_n is the formula of Section 6: it forms $2^n-n-1$ with pow2(n), which is the shift 1ULL << n, and multiplies it by binom(K, n). The function binom(n, k), whose parameter n receives the alphabet size and k the length, returns $0$ when $k$ is outside $0,\dots,n$, replaces $k$ by $\min(k,n-k)$, using the symmetry $\binom nk=\binom n{n-k}$, ^[3] and then, for $i=1,\dots,k$, multiplies result by $n-k+i$ and divides it by $i$. By induction the variable holds $\binom{n-k+i}{i}$ after step $i$, because

$$\binom{n-k+i}{i}=\binom{n-k+i-1}{i-1}\cdot\frac{n-k+i}{i}.$$

The product formed before the division is $i\binom{n-k+i}{i}$, so every division is exact, and the intermediate numbers stay close to the result: for $26$ letters the largest is $13\binom{26}{13}=135207800$.

Counts and products have the type u64, that is std::uint64_t, while sizes, lengths and indices are int. By Section 8 everything for $26$ letters fits with a wide margin, and with --alphabet=5 the program prints $55$, the maximum of Section 6. Up to $42$ letters all products stay exact. From $43$ letters on some $p_m(n)$ exceeds $2^{64}-1$, and since unsigned arithmetic wraps around modulo $2^{64}$ while a shift by $64$ or more bits is undefined, ^[8] the program then prints a wrong value without any warning or, from $64$ letters on, has undefined behaviour.

The Python program has no options and no checkpoint: solve fixes alphabet = 26, multiplies eulerian = 2**n - n - 1 by comb(alphabet, n) from the math module for each $n$, and prints the maximum. Its comment calls $2^n-n-1$ the Eulerian number for exactly one descent; by Section 5 this is the same count as for exactly one ascent. Python integers have unlimited precision, so no overflow can occur. ^[9] The Java program follows the C++ one without its options and checkpoint: binom uses the same loop with long, a signed 64-bit type whose largest value is $2^{63}-1$, ^[9] and main computes (1L << n) - n - 1 and keeps the maximum with Math.max.

Complexity and Verification

For an alphabet of $m$ letters the C++ program evaluates $m$ values; Python and Java always use $m=26$. For the length $n$, the binom loop of C++ and Java makes $\min(n,m-n)$ iterations of one multiplication and one division, exactly $\lfloor m^2/4\rfloor$ in all, so, counting each 64-bit operation as one step, the time is $O(m^2)$ and the memory $O(1)$. For $m=26$ these are $169$ iterations, plus $3$ for the C++ checkpoint; Python makes $26$ calls of comb on small numbers, and the answer appears instantly. The formula is essential, because the number of strings of different letters, of all lengths from $1$ to $26$, is

$$\sum_{n=1}^{26}\frac{26!}{(26-n)!}\approx1.1\cdot10^{27},$$

far too many to test one by one.

The C++ program checks the value $p(3)=10400$ of the statement before it prints its result, and all three programs print the same number. Separately from the published solutions, brute force confirmed for this article that $a(n)=2^n-n-1$ for every $n\le10$; that for every $n\le12$ the subsets $S$ of Section 4 give each permutation with one ascent exactly once and exactly the $n+1$ sets $\{t+1,\dots,n\}$ are not good; that the insertion rule of Section 5 holds for every permutation with $n\le8$; and, by enumerating strings, the values $p(1),\dots,p(5)$ for $26$ letters and every $p_m(n)$ for alphabets of up to $8$ letters. The Eulerian numbers from their recurrence agree with $2^n-n-1$ for every $n\le26$ and give the same maximum, the ratios $r_m(n)$ decrease strictly for every $m\le60$, and the C++ program prints $55$ and $1596$ with --alphabet=5 and --alphabet=8, the maxima found by enumeration.

Footnotes and References

The references below supply the background facts used above. The description by two descending runs, the count of the first runs and the unimodality argument are derived explicitly in this article.

Project Euler 158 — Lexicographical Neighbours. The official statement gives the examples abc, hat and zyx, states that 10400 strings of three different letters have exactly one character that comes lexicographically after its neighbour to the left, and asks for the maximum of p(n), the count for n ≤ 26 different letters.
Wikipedia — Lexicographic order. Words of equal length are ordered by the alphabetical order of their symbols at the first place where they differ; for one-letter words this is the order of the alphabet.
Wikipedia — Binomial coefficient. C(n, k) is the number of ways to choose an unordered subset of k elements from a set of n elements; the article gives the multiplicative formula and the symmetry C(n, k) = C(n, n − k), which can shorten the calculation.
Wikipedia — Rule of product. If there are a ways of doing one thing and b ways of doing another, there are a · b ways of doing both.
Wikipedia — Eulerian number. A(n, k) counts the permutations of 1 to n with exactly k ascents. The article gives A(n, 1) = 2ⁿ − (n + 1) and the recurrence A(n, k) = (n − k) A(n − 1, k − 1) + (k + 1) A(n − 1, k), and notes that the same numbers count the permutations with k descents.
OEIS A000295 — Eulerian numbers 2ⁿ − n − 1. The terms 0, 0, 1, 4, 11, 26, 57, 120, … count the permutations of {1, 2, …, n} with exactly one descent, for n = 3 the permutations 132, 213, 231 and 312.
C++ — Euler158.cpp. The linked immutable C++ revision contains binom, p_of_n, solve, run_checkpoints and the options --alphabet= and --skip-checkpoints. It is the implementation record for this article.
cppreference — Arithmetic operators. Unsigned integer arithmetic is always performed modulo 2ⁿ, where n is the number of bits of the type, and a shift whose right operand is negative or not less than the number of bits of the left operand has undefined behaviour.
Python — math.comb counts the ways to choose k items from n without repetition and without order, and by Python — numeric types integers have unlimited precision. The Java Language Specification, §4.2.1 gives the range of long, −9223372036854775808 to 9223372036854775807.

Problem 158 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <string>

namespace {

using u64 = std::uint64_t;

struct Options {
    int alphabet = 26;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--alphabet=", options.alphabet)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.alphabet >= 1;
}

u64 binom(const int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    k = std::min(k, n - k);

    u64 result = 1;
    for (int i = 1; i <= k; ++i) {
        result = result * static_cast<u64>(n - k + i) / static_cast<u64>(i);
    }
    return result;
}

u64 pow2(const int exp) {
    return 1ULL << exp;
}

u64 p_of_n(const int alphabet, const int n) {
    const u64 eulerian_n1 = pow2(n) - static_cast<u64>(n) - 1ULL;
    return binom(alphabet, n) * eulerian_n1;
}

u64 solve(const int alphabet) {
    u64 best = 0;
    for (int n = 1; n <= alphabet; ++n) {
        best = std::max(best, p_of_n(alphabet, n));
    }
    return best;
}

bool run_checkpoints() {
    if (p_of_n(26, 3) != 10400ULL) {
        std::cerr << "Checkpoint failed for p(3)" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.alphabet) << '\n';
    return 0;
}

Python

# Problem 158: Exploring strings for which only one character comes lexicographically after its neighbour

from math import comb

def solve():
    alphabet = 26
    best = 0
    for n in range(1, alphabet + 1):
        # Eulerian number for exactly 1 descent in permutation of n distinct elements
        eulerian = 2**n - n - 1
        p = comb(alphabet, n) * eulerian
        best = max(best, p)
    print(best)

solve()

Java

public class Euler158 {
    static long binom(int n, int k) {
        if (k < 0 || k > n)
            return 0;
        k = Math.min(k, n - k);
        long r = 1;
        for (int i = 1; i <= k; i++)
            r = r * (n - k + i) / i;
        return r;
    }

    public static void main(String[] args) {
        int alpha = 26;
        long best = 0;
        for (int n = 1; n <= alpha; n++) {
            long e = (1L << n) - n - 1;
            best = Math.max(best, binom(alpha, n) * e);
        }
        System.out.println(best);
    }
}