<< problem 154 - Exploring Pascal's pyramid | Digital root sums of factorisations - problem 159 >> |

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

(see projecteuler.net/problem=158)

Taking three different letters from the 26 letters of the alphabet, character strings of length three can be formed.

Examples are 'abc', 'hat' and 'zyx'.

When we study these three examples we see that for 'abc' two characters come lexicographically after its neighbour to the left.

For 'hat' there is exactly one character that comes lexicographically after its neighbour to the left.

For 'zyx' there are zero characters that come lexicographically after its neighbour to the left.

In all there are 10400 strings of length 3 for which exactly one character comes lexicographically after its neighbour to the left.

We now consider strings of n <= 26 different characters from the alphabet.

For every n, p(n) is the number of strings of length n for which exactly one character comes lexicographically after its neighbour to the left.

What is the maximum value of p(n)?

# My Algorithm

Each valid string `s`

consists of two sub-strings: `s = left + right`

`left`

and `right`

must be strictly monotonically descending (each letter/character is smaller than its left neighbor)

and there is a "break" between `left`

and `right`

such that the last character of `left`

is bigger than the first character of `right`

.

My function `count(n, alphabet)`

returns the number of words with `n`

characters out of an alphabet of size `alphabet`

(which is 26) that match all conditions.

It considers the simplified case where only the first characters are chosen. That mean that for `n=3`

only `"a"`

, `"b"`

and `"c"`

are taken from the alphabet.

The "break" can be at any position from `2`

to `n-1`

and therefore a simple loop analyzes each possible break:

- there are \binom{n}{i} ways to build `left`

using only `i`

out of the first `n`

characters (see `choose(n, k)`

, taken from problem 116)

- any of the first `n`

characters which are not part of `left`

must be part of `right`

- if the highest `i`

characters are all part of `left`

then there is no break between `left`

and `right`

→ we must not count that combination

To convert the simplified case to the general case, I multiply the `result`

by the number of ways to choose `n`

characters from the whole `alphabet`

.

## Alternative Approaches

I tried a Dynamic Programming approach, too, but had a bug somewhere. The next day I came up with the must simpler version you see below.

## Note

The `for`

-loop can be transformed to a closed formula → speeding up the program.

But the program already finishes all calculations in less than 0.01 seconds, therefore I don't bother with finding the correct formula.

# My code

… was written in C++ and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <iostream>
// number of ways to choose n elements from k available
// code taken from problem 116

unsigned long long choose(unsigned long long n, unsigned long long k)
{
// n! / (n-k)!k!
unsigned long long result = 1;
// reduce overflow by dividing as soon as possible to keep numbers small
for (unsigned long long invK = 1; invK <= k; invK++)
{
result *= n;
result /= invK;
n--;
}
return result;
}
// count number words with n characters

unsigned long long count(unsigned int n, unsigned int alphabet)
{
// invalid parameters: must not use each letter of the alphabet more than once
if (n > alphabet)
return 0;
// count how many word with n characters use the characters 1..n
unsigned long long result = 0;
// there are n places where the "break" between s1 and s2 can occur
// count all possible characters chosen for s1 and s2
for (unsigned int i = 1; i < n; i++)
result += choose(n, i) - 1; // minus 1 because there is always one combination with no break between s1 and s2
// general case: use characters 1..Alphabet instead of 1..n
return result * choose(alphabet, n);
}
int main()
{
// bonus feature: user-defined alphabet size and maximum word length
unsigned int alphabet = 26;
unsigned int size = 3;
std::cin >> alphabet >> size;
// all "words" with 2..size characters
unsigned long long best = 0;
for (unsigned int i = 2; i <= size; i++)
{
unsigned long long current = count(i, alphabet);
// more than before ?
if (best < current)
best = current;
}
std::cout << best << std::endl;
return 0;
}

This solution contains 7 empty lines, 13 comments and 1 preprocessor command.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "26 3" | ./158`

Output:

*Note:* the original problem's input `26 26`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

June 13, 2017 submitted solution

June 13, 2017 added comments

# Difficulty

Project Euler ranks this problem at **55%** (out of 100%).

# Links

projecteuler.net/thread=158 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort.

<< problem 154 - Exploring Pascal's pyramid | Digital root sums of factorisations - problem 159 >> |