Detailed mathematical approach

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)\).

A single ascent forces two decreasing runs

Assume the unique ascent occurs between positions \(k\) and \(k+1\), so

$\pi_k \lt \pi_{k+1}.$

Then every adjacent pair before position \(k\) must be decreasing, and every adjacent pair after position \(k+1\) must also be decreasing. Otherwise we would create a second ascent. So every valid permutation has the shape

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

Equivalently, the permutation is obtained by splitting the set \(\{1,\dots,n\}\) into two nonempty parts:

$A=\{\pi_1,\dots,\pi_k\}, \qquad B=\{\pi_{k+1},\dots,\pi_n\},$

then writing all elements of \(A\) in decreasing order, followed by all elements of \(B\) in decreasing order. Inside each block the order is forced, so the only remaining question is whether the boundary between the two blocks is really an ascent.

Count the admissible splits

There are \(2^n-2\) ways to choose a nonempty proper subset \(A\), with \(B\) determined as its complement. For a given split, the boundary comparison is

$\min(A) \lt \max(B).$

This fails exactly when every element of \(A\) is larger than every element of \(B\). In that case the permutation is globally decreasing and has no ascent at all. The only such bad splits are

$A=\{t+1,t+2,\dots,n\}, \qquad B=\{1,2,\dots,t\}, \qquad 1 \le t \le n-1,$

so there are precisely \(n-1\) of them. Hence

$a(n)=(2^n-2)-(n-1)=2^n-n-1.$

This is also the Eulerian count for permutations with exactly one ascent.

Worked example

Take \(n=4\). Choose \(A=\{4,2\}\) and \(B=\{3,1\}\). Writing both blocks in decreasing order gives

$4,2,3,1,$

and the adjacent comparisons are \(4 \gt 2\), \(2 \lt 3\), \(3 \gt 1\), so there is exactly one ascent.

By contrast, if \(A=\{4,3\}\) and \(B=\{2,1\}\), the resulting permutation is

$4,3,2,1,$

which has no ascent. This is one of the \(n-1\) excluded splits. For \(n=3\), the formula gives \(a(3)=2^3-3-1=4\), so

$p(3)=\binom{26}{3}\cdot 4=10400,$

which is exactly the checkpoint value used by the implementation.

Closed form for \(p(n)\) and the final maximization

Putting the two factors together gives the formula actually evaluated by the code:

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

More generally, for an ordered alphabet of size \(m\),

$p_m(n)=\binom{m}{n}(2^n-n-1).$

The last step is not another combinatorial derivation: the implementations simply evaluate this expression for every admissible \(n\) and keep the largest value. For \(m=26\), the maximizing length is \(18\).

How the Code Works

The C++, Python, and Java implementations all follow the same short pipeline. For each \(n\) from \(1\) to \(26\), they compute the binomial factor \(\binom{26}{n}\), compute the one-ascent factor \(2^n-n-1\), multiply the two to obtain \(p(n)\), and update a running maximum.

None of the implementations generate strings or permutations explicitly. The whole point of the mathematical reduction is that the exponential search space collapses to \(26\) direct evaluations of a closed form.

The C++ and Java versions build the binomial coefficient multiplicatively and use the symmetry \(\binom{n}{k}=\binom{n}{n-k}\) to keep the loop short. The Python version relies on exact integer binomial arithmetic from the standard library. The C++ version also allows the alphabet size to be overridden and includes the sanity check \(p(3)=10400\).

Complexity Analysis

For a general alphabet size \(m\), evaluating one value \(p(n)\) with a multiplicative binomial computation costs \(O(\min(n,m-n))\) time and \(O(1)\) extra space. Sweeping over all \(n=1,2,\dots,m\) therefore costs \(O(m^2)\) time in the direct implementation strategy used here.

For the actual problem size \(m=26\), this is tiny. The important qualitative point is that the algorithm never touches the \(\binom{26}{n}n!\) candidate strings themselves; it counts them symbolically.

Footnotes and References

1. Problem page: Project Euler 158
2. Eulerian numbers: Wikipedia - Eulerian number
3. Binomial coefficients: Wikipedia - Binomial coefficient
4. Ascents and descents in permutations: Wikipedia - Ascents and descents
5. Lexicographic order: Wikipedia - Lexicographic order