# Run-Maximal Strings

## Introduction

Let r(x) return the number of runs in a string x, and let ρ(n) be the maximum number of runs over all strings of length n. Let ρd(n) be the maximum number of runs over all strings of length n with exactly d distinct characters.

## Table of ρd(n) Values -- (d, n-d) Table

We present the ρd(n) values in a table where the columns are indexed by n-d and the rows are indexed by d. The key values are those which fall on the diagonal d = n-d.

The given ρ values are links to records of all the corresponding run-maximal strings. Each string is labelled with either "[pal]" or "[rev]". Consider a canonical representation of a string, in which the first unique character is represented by a, the second by b, and so on. If the canonical representation of the reversal of a string is equal to itself, we call it a p-palindrome, and it labelled "[pal]". (An example is the string "aabb": when reversed it becomes "bbaa", but putting it into canonical form yields the string "aabb" again, so it is a p-palindrome.) If the canonical representation of the reversal of a string is distinct from the original string, we call them "reversible twins". We only list the lexicographically lesser of the twins, and label it with "[rev]". (An example is the string "aab": when reversed it becomes "baa", and putting it into canonical form yields the string "abb", which is distinct from the original. "aab" and "abb" are reversible twins.)

 n-d 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 d 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 3 4 5 5 6 7 8 8 10 10 11 12 13 14 15 15 16 17 18 19 20 21 22 23 24 25 26 27 27 28 29 30 30 31 32 33 35 35 36 37 38 39 40 41 42 43 44 45 46 46 47 48 49 50 51 52 53 54 55 56 56 57 58 59 60 61 62 63 64 3 1 2 3 3 4 5 6 6 7 8 9 10 11 11 12 13 14 15 16 16 17 18 19 20 21 22 23 24 25 26 27 28 28 29 30 31 31 32 33 35 36 36 4 1 2 3 4 4 5 6 7 7 8 9 10 11 12 12 13 14 15 16 17 17 18 19 20 21 22 23 24 25 26 27 28 29 29 5 1 2 3 4 5 5 6 7 8 8 9 10 11 12 13 13 14 15 16 17 18 18 19 20 21 22 23 24 25 6 1 2 3 4 5 6 6 7 8 9 9 10 11 12 13 14 14 15 16 17 18 19 19 20 21 7 1 2 3 4 5 6 7 7 8 9 10 10 11 12 13 14 15 15 16 17 18 19 20 8 1 2 3 4 5 6 7 8 8 9 10 11 11 12 13 14 15 16 16 17 18 19 9 1 2 3 4 5 6 7 8 9 9 10 11 12 12 13 14 15 16 17 17 18 10 1 2 3 4 5 6 7 8 9 10 10 11 12 13 13 14 15 16 17 18 11 1 2 3 4 5 6 7 8 9 10 11 11 12 13 14 14 15 16 17 18 19 12 1 2 3 4 5 6 7 8 9 10 11 12 12 13 14 15 15 16 17 18 19 20 13 1 2 3 4 5 6 7 8 9 10 11 12 13 13 14 15 16 16 17 18 19 20 21 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 14 15 16 17 17 18 19 20 21 22 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 15 16 17 18 18 19 20 21 22 23 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 16 17 18 19 19 20 21 22 23 24 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 18 19 20 20 21 22 23 24 25 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18 19 20 21 21 22 23 24 25 26 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 20 21 22 22 23 24 25 26 27 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 21 22 23 23 24 25 26 27 28 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 22 23 24 24 25 26 27 28 29 22 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 22 23 24 25 25 26 27 28 29 30 23 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 23 24 25 26 26 27 28 29 30 31

This information can also be presented in a (d, n-2d) table.

## Change Log

September 6, 2011 - Added link to (d, n-2d) table.

May 9, 2011 - Inserted unlinked entries calculated based on other entries in the table.

August 27, 2010 - Added links to the distinct run-maximal string generated for each ρd(n), and description of record notation.

June 14, 2010 - Chart posted.