The best riddles. Anywhere.

## Riddle: A Precisely Ordered String

Consider a 10-character string consisting of the numbers 0 through 9, with each number appearing exactly once, such that each number (except for the left-most number) is within 1 of SOME number to its left (e.g. we would say that 6 is within 1 of 5 and 7. Note that 0 is NOT within 1 of 9, i.e. we don't wrap around from 9 to 0).

So as an example, 3452671089 is a such a string, because for any number in it (except for the 3 all the way on the left), you can find a number to its left that is with 1 of it. For example, if you look at the number "8", then you can find the number "7" to its left, which is within 1 of it.

Another valid string is 0123456789, which again follows this rule.

An example of an invalid string is 1023457689, because if you look at the number "7", there is no number to its left that is within 1 of it (which would be 6 or 8).

How many 10-character strings are there that meet the described criteria?

There are certain numbers that you could not possibly put in certain parts of the string.