# Description

Given a length n, and an alphabet size k>0, your program must determine the number of strings with those parameters which have a maximal number of unique substrings. In the case of k=2, this generates OEIS A134457.

# Example

For example, 2210 has the substrings  , 2, 22, 221, 2210, 2, 21, 210, 1, 10, and 0, for a total of 11. However, 2 appears twice, so it only has 10 unique substrings.

This is as many as possible for a length 4 string containing 3 different symbols, but it ties with 35 other strings for a total of 36 tieing strings including 0012, 2101, and 0121. Therefore, for n=4 and k=3, your program should output 36.

# Test Cases

n    k    output

0    5    1
1    3    3
5    1    1
9    2    40
2    3    6
5    5    120

• Could you please give some examples? It's kind of hard to follow the challenge from that very short description. Jul 8, 2017 at 15:09
• So wouldn't n=2, k=3 output 9: 11,12,21,22,31,32,33,13,23? Jul 9, 2017 at 9:53
• @veganaiZe The double digits have a repeated substring. Jul 9, 2017 at 19:43

# Pyth, 12 bytes

l.Ml{.:Z)^UE


Try it online.

Pure brute force.

### Explanation

• Implicit: append Q to the program.
• Implicit: read and evaluate a line of input (n) in Q.
• E: read and evaluate a line of input (k).
• U: get a range [0, ..., k-1].
• ^: get all n-length strings of [0, ..., k-1].
• .M: find the ones that give a maximum for function f(Z):
• .:Z: find the substrings of Z
• {: remove duplicates
• l: get the number of unique substrings
• l: get the number of such strings

# Jelly, 9 bytes

ṗµẆQLµ€ML


Try it online!

Input in reversed order. Brute force.

• Save a byte by avoiding the three-atom chain with a transpose and tail: ṗẆQ$€ZṪL Jul 8, 2017 at 16:25 # Mathematica, 96 bytes Last[Last/@Tally[Length@Union@Flatten[Table[Partition[#,i,1],{i,s}],1]&/@Tuples[Range@#2,s=#]]]&  ## Haskell, 82 bytes import Data.Lists l=length n#k=l$argmaxes(l.nub.powerslice)$mapM id$[1..k]<$[1..n]  Usage example: 9 # 2 -> 40. How it works:  [1..k]<$[1..n]  --  make a list of n copies of the list [1..k]
mapM id          --  make a list of all combinations thereof, where
--  the 1st element is from the f1st list, 2nd from 2nd etc
argmaxes             --  find all elements which give the maximum value for function:
l.nub.powerslice  --    length of the list of unique sublists
l                      --  take the length of this list