Statement

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 $\leq$ 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)?

Solution

The solution for this problem is achieved using DP.

I used a top-down approach with memoization. The dp dictionary will be indexed by three things: length, number of numbers which are greater than the previous and the number of times that the a[i] < a[i+1].

The base cases are:

• (0, 0, 0) = 0: Meaning we finished choosing the strings but no a[i] < a[i+1] so its not valid.
• (0, 0, 1) = 1: Meaning we finished choosing the strings and there's only one occurrence where a[i] < a[i+1] so its valid and there's only one possibility.
• (_,_,2) = 0: Any case where there is more than one occurrence where a[i] > a[i+1] is not valid so 0 is returned.

In my python code I implemented a method get_num that receives the 3 indexes. It first checks if the result is in the dp dictionary, in that case returns the saved value; if the 3rd index is greater than 1 it returns 0.
If none applies it calls recursively for each case that we could pick from, adds them all up and stores the value for not recalculating it.

It is important to notice that we don't need to take the 26 possible characters to calculate the different number of ways of generating different strings of length x. We just calculate from the base that we have x characters and then multiply the result by the number of combinations we can take x from 26.

factorial = {0:1}
for i in range(1, 27):
    factorial[i] = factorial[i-1] * i
 
dp = {
    (0, 0, 0) : 0,
    (0, 0, 1) : 1
}
def get_num(*args):
    if args in dp:
        return dp[args]
 
    length, num_greater, count = args
    if count > 1:
        return 0
    result = sum(get_num(length-1, i, count + ((i < num_greater) and 1 or 0)) for i in range(length))
    dp[args] = result
    return result
 
p = lambda n: sum(get_num(n-1, i, 0) for i in range(n)) * (factorial[26] // (factorial[n] * factorial[26 - n]))
 
if __name__ == '__main__':
    max_pn, max_n = max((p(n), n) for n in range(2, 27))
    print("The result is:", max_pn, "found at n:", max_n)

I applied the same techniques to translate the code into a Haskell program:

import Data.Map
import Data.Maybe

factorial n = factorial' n 1
    where
        factorial' n res
            | n < 2 = res
            | n >= 2 = factorial' (n-1) (res * n)

comb x y = ((factorial x) `div` ((factorial y) * (factorial (x-y))))

getValue :: (Integer, Integer, Integer) -> Map (Integer, Integer, Integer) Integer -> (Integer, Map (Integer, Integer, Integer) Integer )
getValue (length, greater, count) dp
    | count > 1 = (0, dp)
    | member (length, greater, count) dp = (fromJust (Data.Map.lookup (length, greater, count) dp), dp)
    | notMember (length, greater, count) dp = getValue' (length, greater, count) dp 0 0
        where
            getValue' (length, greater, count) dp i res
                | i == length = (res, insert (length, greater, count) res dp)
                | i < length = getValue' (length, greater, count) nDp (i+1) (res + nRes)
                where
                    nCount = if i < greater then count+1 else count
                    (nRes, upDp) = getValue ((length -1), i, nCount) dp
                    nDp = insert ((length -1), i, nCount) nRes dp

p :: Integer -> Map (Integer, Integer, Integer) Integer -> (Integer, Map (Integer, Integer, Integer) Integer)
p n dp = p' 0 dp 0
    where
        p' x dp res 
            | x == n = (res * (comb 26 n), dp)         
            | x < n  = p' (x + 1) nDp (res + nRes)
            where
                (nRes, nDp) = getValue ((n-1), x, 0) dp

initialDp = fromList [((0,0,0), 0), ((0,0,1), 1)]

main = print (first (foldl f (0, initialDp) [1..26]))
    where
        first (x, y) = x
        f (r, dp) n = 
            let
                (nRes, nDp) = p n dp
                maxR = max r nRes
            in
                (maxR, nDp)