Maximum number of distinct substrings

Question

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

Answer 1

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

Answer 2

Jelly, 9 bytes

ṗµẆQLµ€ML

Try it online!

Input in reversed order. Brute force.

Answer 3

Mathematica, 96 bytes

Last[Last/@Tally[Length@Union@Flatten[Table[Partition[#,i,1],{i,s}],1]&/@Tuples[Range@#2,s=#]]]&

Answer 4

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