Let an alphabet $A$ with card $A=q\geq 1$ be given. A factor (subword) $u$ of an infinite sequence or finite word $w$ has the right valence $j$ if there are $j$ and only $j$ distinct letters $x_{i}$ such that $ux_{i},1\leq i\leq j$ are also in $F(w)$ (the set of all the subwords, or factors, of $w$ ); if a factor has the right valence $j$ it can be extended on the right in exactly $j$ ways. The left valence is defined in a similar way. A factor having the right (left) valence $\geq 2$ is called right (left) special; a factor which is both right and left special is called bispecial. The length of a word $w$ will be denoted by $|w|$.

For an infinite sequence $U$ any factor $u$ can always be extended on the right in a factor of $U$. For a finite word $w$ there are subwords which cannot be extended on the right. Such words have to be suffixes of $w$. Let us denote by $w_{0}$ the suffix of $w$ of minimal length which cannot be extended on the right and by $K$ the length of $w_{0}$. Then any other subword $\lambda w_{0}$ also cannot be extended on the right. Considering the prefix of $w$ of minimal length which cannot be extended on the left, we shall denote its length by $H$. The constants $K$ and $H$ were defined by de Luca [15].

Let us denote by $S_{0}(w)$ the set of all suffixes of $w$ which cannot be extended on the right in $F(w)$, i.e., their right valence is 0 . If the length of $w$ is $N$, then we set for any $0\leq n\leq N$

For all $0\leq n\leq N$, one has $s_{0}(n)\leq 1$. Moreover, $K$ being the length of $w_{0}$ (the suffix of $w$ of minimal length which cannot be extended on the right), $s_{0}$ is given by

It follows that the number of subwords which cannot be extended on the right is

For an infinite sequence $U$, the (subword) complexity function $p_{U}:\mathbb{N}\longrightarrow\mathbb{N}$ (defined in [17] as the block growth, then named subword complexity in [6]) is given by $p_{U}(n)=\operatorname{card}\left(F(U)\cap A^{n}\right)$ for $n\in\mathbb{N}$, so it maps each nonnegative number $n$ to the number of factors of length $n$ of $U$; it verifies the iterative equation

$s(j,n)$ being the cardinal of the set of the factors of $U$ having the length $n$ and the right valence $j$.

For a finite word $w$ of length $N$, the complexity function $p_{w}:\mathbb{N}\longrightarrow\mathbb{N}$ given by $p_{w}(n)=\operatorname{card}\left(F(w)\cap A^{n}\right),n\in\mathbb{N}$, has the property that $p_{w}(n)=0$ for $n>N$. The corresponding iterative equation is

Since $s_{0}(n)=s(0,n)$ we can write (2) in a condensed form

The above relations have their correspondents in terms of left extensions of the subwords.

For a finite word $w$ of length $N$ over the alphabet $A$ with card $A=q$, the subword complexity $p_{w}(n)$ will be less than or equal to the number $q^{n}$ of all the possible words of length $n$ over the $q$-letter alphabet and also less than or equal to the number $N-n+1$ of all occurrences of subwords of length $n$ in $w$. The map $h:\{0,1,\ldots,N\}\longrightarrow\mathbb{N}$ defined in [15]

will have values greater than or equal to those of any complexity function $p_{w}$ for $w\in A^{N}$, i.e., $p_{w}(n)\leq h(n),n\in\{0,1,\ldots,N\}$. The fact that $p_{w}(n)\leq N-n+1$ was stated in [11], while $p_{w}(n)\leq h(n)$ appeared in [20].

We recall that for infinite sequences $U$ one has

and that there exist sequences, called complete, for which the complexity is precisely $q^{n}$ for all $n\in\mathbb{N}$. An example is the Champernowne sequence
0.1.10.11.100.101.110.111.1000. …
containing successively all the nonnegative integers written in base 2 , and, more generally, in base $q$ (it was used in [4] to construct a normal number in base ten).

Remark 1. We mention at first the trivial case when $q=1$, for which $h(n)=1$ for all $n\in\{0,1,\ldots,N\}$; there is a word, namely $w_{1}=a^{N}$, whose complexity satisfies $p_{w_{1}}(n)=1$ for all $n\in\{0,1,\ldots,N\}$.

For $n\geq 1,q\geq 2$ and $N\leq q$, we have

hence $h(n)=N-n+1$ for all $n\in\{1,\ldots,N\}$. For each word $w_{2}$ containing $N\leq q$ distinct elements of $A$ the complexity function is $p_{w_{2}}(n)=N-n+1$ for all $n\in\{1,\ldots,N\}$, and $p_{w_{2}}(0)=h(0)=1$, hence in this case it also coincides with $h$.

In what follows we shall consider $q\geq 2$ and $N>q$. The values of the function $h$ are given by the minimum of the values of an increasing exponential and of a descending line, so at the beginning $h$ will follow the exponential, and then the descending line. The following result is presented without proof in [15]:

Proposition 1. If $e_{N}$ denotes the first point where ( $e_{N},h\left(e_{N}\right)$ ) is on the descending line, the maximum $h_{\max}$ of the function $h$ is attained at $e_{N}$, and $e_{N}$ is given by $\left[\log_{q}N\right]$ or $\left[\log_{q}N\right]+1$ (for a real $x$, $[x]$ denotes the largest integer which is less than or equal to $x$ ).

We shall determine precisely the point $\left(e_{N},h\left(e_{N}\right)\right)$ where the maximum of the function $h$ is taken.

Proposition 2. Let $e_{N}=\min\{m\in\{1,\ldots,N\}:h(m)=N-m+1\}$. If $N\in\mathbb{N}$ is given so that $q^{k}+k<N<q^{k+1}+k+1$, then $e_{N}=k+1$ and this is the unique point where $h$ attains its maximum $N-k$; for $N=q^{k}+k$, we have $e_{N}=k+1$ and the function $h$ attains its maximum $N-k$ at both $e_{N}$ and $e_{N}-1$.

In fact, if $q^{k}+k\leq N<q^{k+1}+k+1$, the function $h$ is given by

and $h_{\max}=N-k=h(k+1)$, for $N=q^{k}+k$ the maximum being attained also at the point $k$.

Proof. Let $N\in\mathbb{N}$ be given so that $q^{k}+k\leq N<q^{k+1}+k+1$. The function $h$ being increasing on $\left\{0,1,\ldots,e_{N}-1\right\}$ and decreasing on $\left\{e_{N},\ldots,N\right\}$, we have only to compare its values on $e_{N}-1$ and $e_{N}$. From the definition of $h$ and of $e_{N}$ we have

and

which means that

But $h\left(e_{N}-1\right)=q^{e_{N}-1}$ and $h\left(e_{N}\right)=N-e_{N}+1$, hence from (6) it follows that the maximum of $h$ is taken at $e_{N}$. The function $f(x)=q^{x}+x$ being increasing, from (8) one obtains $e_{N}=k+1$ and $h\left(e_{N}\right)=N-k$.

If $q^{k}+k<N<q^{k+1}+k+1$ we have $h(k+1)>h(k)$, so $e_{N}=k+1$ is the unique point where $h$ attains its maximum which is equal to $N-k$; if $N=q^{k}+k$, we have $h(k+1)=h(k)$, so the maximum $N-k$ of $h$ is taken at two points $e_{N}=k+1$ and $e_{N}-1$.

The description of $h$ given in (5) was established in [12]. The value of $e_{N}$ being related to the integer part of $\log_{q}N$, we can give a more precise result than that in the above Proposition 1.

Remark 2. For $q^{k}+k\leq N<q^{k+1}+k+1$, we have $k=\left[\log_{q}N\right]$ for $q^{k}+k\leq N<q^{k+1}$, and $k+1=\left[\log_{q}N\right]$ for $q^{k+1}\leq N<q^{k+1}+k+1$; it follows that in the first case $e_{N}=\left[\log_{q}N\right]+1$, and in the second case $e_{N}=\left[\log_{q}N\right]$.

Given the number $N$, the maximum of the function $h$ can be easily determined.

Example 1. Let $N=6,q=2$; we obtain $e_{N}=3$ and $h_{\text{max }}=4=h(2)=h(3)$. For $N=7,q=2$, we have $e_{N}=3$ and $h_{\text{max }}=5=h(3)$.

For an infinite sequence $U$, the complexity function $p_{U}$ is nondecreasing; if there exists $m\in\mathbb{N}$ such that $p_{U}(m+1)=p_{U}(m)$, then $p_{U}$ is constant for $n\geq m$. The complexity function for a finite word $w$ of length $N$ has obviously a different behaviour, because of $p_{w}(N)=1$ (there is a unique factor of length $N$, namely $w)$. The study of the shape of $p_{w}$ was considered by Heinz [11] and then by de Luca in [15], the results in [15] being briefly exposed in what follows. Then the piecewise monotonicity of $p_{w}$ is established in Theorems 5 and 6.

Let us consider for $n\in\{0,\ldots,N\}$ the number $R_{w}(n)$ of all right special factors of length $n$. Any suffix of a right special factor is still a right special factor. Since $R_{w}(N-1)=R_{w}(N)=0$, one can define an integer $R$ by

One has $0\leq R\leq N-1$; thus $R-1$ represents the maximal length of a right special factor of $w$ (excepting the case of the word $a^{N}$ which has no special factor and for which $R=0$ ). If $R=1$, in $w$ there are no right special factors of length $n\geq 1$; such an example is $w=(ab)^{k},k\geq 1$. Similarly, there exists a number $0\leq L\leq N-1$ so that $L-1$ represents the maximal length of a left special factor of $w$ (except if $w=a^{N}$ ). Remember the number $K(H)$ representing the minimal length of a suffix (prefix) of $w$ which cannot be extended on the right (left). The numbers $K$ and $R$ (or their duals $H$ and $L)$ play an important role in the description of the shape of $p_{w}$.

Let us denote

The function $r$ has the property that $r(n)>0$ for $n\in[0,R-1]$, and $r(n)=0$ for $n\in[R,N]$. The recurrence relation (2) can be written as

If $R<K$, for $n\in[0,R-1]$ one has $s_{0}(n)=0$ and $r(n)>0$. From (9) we obtain that $p_{w}$ is strictly increasing on $[0,R]$. For $n\in[R,K-1],s_{0}(n)=0$ and $r(n)=0$, so $p_{w}$ is constant on the interval $[R,K]$. For $n\in[K,N-1]$, $s_{0}(n)=1$ and $r(n)=0$, so $p_{w}$ is strictly decreasing on $[K,N]$, and, moreover, for $n\in[K,N-1],p_{w}(n+1)=p_{w}(n)-1$.

If $R\geq K$, for $n\in[0,K-1]$ we obtain $s_{0}(n)=0,r(n)>0$, so from (9) $p_{w}$ will be strictly increasing on $[0,K]$. For $n\in[K,R-1],s_{0}(n)=1$ and $r(n)>0$, hence $p_{w}$ is non-decreasing on $[K,R]$. For $n\in[R,N-1]$ one has $s_{0}(n)=1$ and $r(n)=0$, which implies that $p_{w}$ is strictly decreasing on $[R,N]$ and, for $n\in[R,N-1],p_{w}(n+1)=p_{w}(n)-1$.

It follows
Proposition 3. [15]. The subword complexity $p_{w}$ takes its maximum at $R$ and, moreover,

Proof. In both cases analyzed above, $p_{w}$ has its maximum at $R$. If $R\geq K$, $p_{w}(n+1)=p_{w}(n)-1$ for all $n\in[R,N-1]$, so $1=p_{w}(N)=p_{w}(R)-(N-R)$ and then $p_{w}(R)=N-R+1$. If $R<K,p_{w}(n+1)=p_{w}(n)-1$ for all $n$ in $[K,N-1]$ and $1=p_{w}(N)=p_{w}(K)-(N-K)$. Since $p_{w}(K)=p_{w}(R)$ the result follows.

In a similar way, one can prove
Proposition 4. [15]. The subword complexity $p_{w}$ takes its maximum at $L$ and, moreover,

hence $\max\{R,K\}=\max\{L,H\}$.
From the analysis before Proposition 3, we have the following information on the shape of the function $p_{w}$ [15]:

For $R<K$, it is strictly increasing (starting from $p_{w}(0)=1$ and $p_{w}(1)=q=\operatorname{card}A$ ), then constant, and then strictly decreasing (with $p_{w}(n+1)=p_{w}(n)-1$ on the last interval).

For $R\geq K,p_{w}$ is at first strictly increasing, then non-decreasing, and at last strictly decreasing also with $p_{w}(n+1)=p_{w}(n)-1$.

So in both cases, there is an interval on which $p_{w}$ is increasing and one on which $p_{w}$ is strictly decreasing. The only problem is that in the second case it could be that after becoming constant, $p_{w}$ would increase again. We show that this is not the case.

Let us consider $n\in[K,R-1]$, so $s_{0}(n)=1,r(n)>0$ and $p_{w}(n+1)\geq p_{w}(n)$. Suppose that there exists $n$ so that

From (10) one obtains that $s(2,n)=1$ and $s(j,n)=0$ for $j\geq 3$, i.e., there exists a unique right special factor having length $n$, and its valence is 2 : let it be denoted $v_{n}$. From (11) it follows that

which is possible for two situations:
I. $s(2,n+1)=2$;
II. $\exists j\geq 3,s(j,n+1)\neq 0$.

If II. is true, there will be a right special factor of length $n+1$ having valence at least 3, and then the factor obtained by excluding its first letter will have length $n$ and valence at least 3 , contradicting the uniqueness of $v_{n}$.

If I. is true, there will exist two different right special factors of length $n+1$ and valence at least 2 . They can differ only by their first letter, otherwise there would exist two different factors of length $n$ and valence 2 . So they will have the form

i.e., $v_{n}$ will be bispecial, and in the word $w$ there will be also

The subword $v_{n}$ cannot be a suffix of $w$ since $v_{n}$ is extendable to the right and there is no extendable suffix of length greater than or equal to $K$. Let us consider the last occurrence of $v_{n}$, suppose it is followed by $c$. Then

and, $v_{n}c$ being left special, $v_{n}c$ will have another occurrence in $w$, so

Let $u$ be the longest common prefix of $v_{n}cz_{2}$ and $v_{n}cz_{2}^{\prime}$, which will satisfy

Since the subword $u$ is a proper prefix of $v_{n}cz_{2}^{\prime},u$ is right extendable; then it cannot be a suffix of $w$, hence it is also a proper prefix of $v_{n}cz_{2}$, and thus right special. The suffix of length $n$ of $u$ is then right special, in contradiction with the fact that the last occurrence of $v_{n}$, the unique right special factor of length $n$, was chosen so that $w=z_{1}v_{n}cz_{2}$. It follows that in the case $K<R$, if $p_{w}(n)=p_{w}(n+1)$ for a value $n\geq K$, then $p_{w}$ will remain constant until it will begin (at $R$ ) to decrease to 1 (it cannot start increasing again). We mention that Heinz [11] proved that from $p_{w}(n)=p_{w}(n+1)$ and $N>p_{w}(n)+n$ it follows $p_{w}(n)=p_{w}(n+2)$.

Let us denote by $J$ the smallest number greater than or equal to $K$ for which $w$ has precisely one right special factor of that length, with valence 2 (if this is not the case, take $J=R$ ). We have established the following

Theorem 5. For a finite word of length $N$, the complexity function is at first strictly increasing, then constant and at last decreasing having the slope -1 . If $R<K$, the successive intervals are $[0,R],[R,K]$ and $[K,N]$, while for $R\geq K$ they are $[0,J],[J,R]$ and $[R,N]$.

One can easily avoid to analyze two cases by simply considering instead of a word $w\in A^{N}$, a word $W\in(A\cup\{*,\#\})^{N+2}$ obtained by adding two different symbols which are not in $A$ at the beginning and at the end of $w$, i.e., $W=*w\#$. The complexity functions for $w$ and $W$ are related by $p_{W}(n)=p_{w}(n)+2$ for $n\in\{1,\ldots,N+1\}$ (and obviously $p_{W}(N+2)=1$ ). So the graph of $p_{W}$ is the graph of $p_{w}$ shifted by two units parallel to the $y$-axis,
and the two functions have the same monotonicity. For $W$ we have $K_{W}=1$, $R_{W}\geq R_{w}$ and, similarly, $H_{W}=1,L_{W}\geq L_{w}$, hence in this case we have always $R_{W}\geq K_{W}$; from Proposition 4 it follows also $R_{W}=L_{W}$. The advantage of considering the word $W$ is that instead of the four parameters $K,H,R,L$ we are left with only one, namely the common value $M$ of $R_{W}=L_{W}$. Denoting by $J$ the smallest positive number for which $W$ has precisely one right special factor of that length, with valence 2 (if there is not such a factor, $J=M$ ), we obtain

Theorem 6. For a finite word $w$ of length $N$, the intervals of monotonicity of $p_{w}$ are $[0,J],[J,M]$ and $[M,N]$, the function increasing at first, being constant and then decreasing with the slope -1 ; the maximum of $p_{w}$ is $p_{w}(M)=N-M+1$. The numbers $J$ and $M$ are those defined above for the word $W=*w\#$.

Example 2. Let $w=babbabbbaa$, so $N=10,K=2,R=5,H=5,L=4$, $J=4,M=5$. In this case $p_{w}(0)=1,p_{w}(1)=2,p_{w}(2)=4,p_{w}(3)=5$, $p_{w}(4)=6$, and $p_{w}(n)=11-n$ for $n\in\{5,\ldots,10\}$.

For $w=aababbabab$, we have $N=10,K=5,R=4,H=2,L=5,J=4$, $M=5$ and $p_{w}(0)=1,p_{w}(1)=2,p_{w}(2)=4,p_{w}(3)=5,p_{w}(4)=6$, and $p_{w}(n)=11-n$ for $n\in\{5,\ldots,10\}$.

REMARK 3. For the words in example 2, the function $p_{w}$ is concave on $[1,N]$, i.e.,

However this is not the rule, as the following examples show for both $K<R$ and $K>R$.

Example 3. Let $w=abbabbbaaba$, so $N=11,K=3,R=4,H=4,L=4$, $J=4,M=4$. In this case $p_{w}(0)=1,p_{w}(1)=2,p_{w}(2)=4,p_{w}(3)=7$, and $p_{w}(n)=12-n$ for $n\in\{4,\ldots,11\}$.

Let $w=abbabbbaababbba$, so $N=15,K=7,R=4,H=4,L=7,J=4$, $M=7$. In this case $p_{w}(0)=1,p_{w}(1)=2,p_{w}(2)=4,p_{w}(3)=7,p_{w}(4)=p_{w}(5)=p_{w}(6)=p_{w}(7)=9$, and $p_{w}(n)=16-n$ for $n\in\{8,\ldots,15\}$.

We mention that the refinement of de Luca’s result has been proved independently by Levé and Séébold [14] while studying $k$-reachable integers.

In section 2 we found the point where the function $h$ takes its maximum. A problem to be considered is the following: are there any words $w$ of length $N$ such that $h\left(e_{N}\right)=\max\left\{p_{w}(n):n\in\{0,\ldots,N\}\right\}$ ? If such words do exist, they have the property that the maximum of their complexity function cannot be exceeded by the maximum of the complexity function of any other word of length $N$.

The answer to this problem is in affirmative and it relies on the following result which was stated by Good in [10] for $q=2$. The enumeration of the words whose existence is proved was given by de Bruijn [2], who later [3] acknowledged the priority of C. Flye Sainte-Marie [7].

Lemma 7. Given an alphabet $A$ with card $A=q$, for each $k\in\mathbb{N}$ the shortest word containing all the $q^{k}$ words of length $k$ has $q^{k}+k-1$ letters.

Proof. The existence of such a word (which is usually named de Bruijn word of order $k$ ) is proved by considering the de Bruijn graph $B_{k-1}$ (which is strongly connected) with $q^{k-1}$ vertices labelled with the elements of $A^{k-1}$, and $q^{k}\operatorname{arcs}($ an $\operatorname{arc}$ from $u$ to $v$ exists if and only if there exist two letters $x,y\in A$ such that $\left.ux=yv\in A^{k}\right)$. Each vertex has the same number $q$ of inward and outward arcs; therefore, there exists an Eulerian cycle, and each path, starting from any vertex and following the cycle until coming back to that vertex, will provide a word (obviously the shortest) of length $q^{k}+k-1$ which contains exactly one occurrence of all the $q^{k}$ words of length $k$. The word of length $q^{k}+k-1$ is often identified with the cycle formed by its first $q^{k}$ letters.

Remark 4. For the de Bruijn word of order $k$, whose existence was proved in Lemma 7, we have $R=K=J=k$, and the maximum of its complexity function is attained at $k$ and equals $q^{k}$. Such a word can be represented in the form $x_{1}\ldots x_{q^{k}}\ldots x_{q^{k}+k-1}$ (with $x_{q^{k}+1}\ldots x_{q^{k}+k-1}=x_{1}\ldots x_{k-1}$ ), or as a cycle $\left(x_{1}\ldots x_{q^{k}}\right)$ or as an infinite periodic sequence with the period $q^{k}$.

The first algorithm which constructs such a word was given by Martin [16]. Considering the alphabet $A=\left\{i_{1},\ldots,i_{q}\right\}$, the algorithm in question is built up out the following three rules.
I. Each of the first $k-1$ symbols is chosen equal to $i_{1}$.
II. The symbol $a_{m}$ to be added to the sequence $a_{1}a_{2}\ldots a_{k}\ldots a_{m-k+1}\ldots a_{m-1}$, where $a_{1}=\ldots=a_{k-1}=i_{1},m\geq k$ and the $a$ ’s stand for the $i$ ’s in a certain order, is the $i_{j}$ with the greatest subscript consistent with the requirement that the section $a_{m-k+1}\ldots a_{m-1}a_{m}$ duplicate no previously occurring section of $k$ symbols in the above sequence.
III. Rule II. is first applied for $m=k$ (in which case $a_{m}=a_{k}=i_{q}$ ) and is then applied repeatedly until a further application is impossible.

This algorithm needs a very large memory (for all the subwords of length $k$ which have already been obtained), but there exist also some memoryless algorithms exposed, for example, in [8], [9] and [18].

We can prove now
Theorem 8. For each $N\in\mathbb{N}$, there exists a word of length $N$ over an alphabet $A$ with $\operatorname{card}A=q$ for which the maximum of the complexity function is equal to the maximum $h_{\max}$ of $h$; the maximum is taken at the same points for both functions. Such words can be easily constructed using the de Bruijn words.

Proof. Keeping in mind the considerations in Remark 1, which mean precisely that the theorem is true for $q=1$ and for $q\geq 2,N\leq q$, we shall consider $q\geq 2$ and $N>q$. Let $k$ be the unique natural number so that

If $N=q^{k}+k$, we apply Lemma 7 for $k$, obtaining a word of length $N-1$ containing as factors all the $q^{k}$ words of $k$ letters, and $q^{k}-1$ distinct words of length $k+1$. The word $v$ obtained by adding a letter from $A$ at its end will contain $q^{k}$ words of $k$ letters and $q^{k}$ distinct words of length $k+1$, hence $p_{v}(k)=p_{v}(k+1)=N-k$. This is the maximum of the function $p_{v}$, it is equal to $h_{\text{max }}$ and it is attained at the same points as the maximum of $h$ given in Proposition 2. Actually, in this case we have $p_{v}=h$.

Let us now consider the case $N=q^{k+1}+k-m,m\in\left\{0,1,\ldots,q^{k+1}-q^{k}-\right.1\}$. Applying Lemma 7 for the number $k+1$, we obtain a shortest word $w$ containing all the $q^{k+1}$ words of length $k+1$, having $q^{k+1}+k$ letters. So for each $m\in\left\{0,1,\ldots,q^{k+1}-q^{k}-1\right\}$, the prefix $w_{m}$ of $w$ obtained by deleting $m$ final letters will satisfy $p_{w_{m}}(k+1)=q^{k+1}-m>q^{k}\geq p_{w_{m}}(k)$, this being the maximum of the complexity function for the considered word. The maximum is attained only for $k+1$.

Applying Proposition 2 for $N=q^{k+1}+k-m$ we obtain $h_{\text{max }}=h(k+1)=q^{k+1}+k-m-k=q^{k+1}-m$, which means that the maximum of the complexity function for $w_{m}$ is equal to the maximum of the complexities of all possible words of length $q^{k+1}+k-m$.

Example 4. Let us consider for the 2-letter alphabet $A=\{a,b\}$ the values $N=6$ and $N=7$. For $N=6=2^{2}+2$ we have $k=2$ and, by adding a letter (for example $a$ ) to the Martin word of order 2, abbaa, we obtain $v=abbaaa$; the maximum of $p_{v}$ is $p_{v}(2)=p_{v}(3)=4$. For $N=7=2^{2}+3$ we can consider the Martin word of order 3, aabbbabaaa, and delete three symbols from the end. The word $w_{3}=aabbbab$ has the maximum of its complexity function given by $p_{w_{3}}(3)=5$.

The maximum of the function $h$ for $N=6$ and $N=7$ was calculated in Example 1 and it coincides with that of $p_{v}$, respectively $p_{w_{3}}$ and is taken at the same points.

An interesting problem is: Let $q\geq 1$ and $N\in\mathbb{N}$ be given and the function $h:\{0,1,\ldots,N\}\longrightarrow\mathbb{N}$ defined as in (4). Is there a word $w$ of length $N$ over the $q$-letter alphabet $A$ such that

i.e., $h$ is the complexity function for that word? If such a word does exist, how can it be constructed?

The question has an affirmative answer for the trivial cases $q=1$ and $q\geq 2$, $N\leq q$, mentioned in Remark 1, so it has to be studied for $q\geq 2,N>q$. In the proof of Theorem 8 it was shown that, given the number $N=q^{k}+k,k\geq 1$, there exists a word $v$ of length $N$ containing $q^{k}$ distinct words of length $k+1$, and also $q^{k}$ words of length $k$. This means that $h$ and $p_{v}$ coincide on $k$ and $k+1$. One the one hand, $p_{v}(k)=h(k)=q^{k}$ means that $v$ contains all possible words of length $k$ as factors, and this implies that it also contains all possible words of shorter lengths, hence $h(n)=p_{v}(n)=q^{n}$ for $n\in\{0,1,\ldots,k\}$. On the other hand, $p_{v}(k+1)=h(k+1)=N-k$ means that each of the $N-k$ factors of length $k+1$ of $v$ occurs exactly once, as there are precisely $N-k$ available positions for a factor of this length, and this implies that longer factors occur only once too, hence $h(n)=p_{v}(n)=N+1-n$ for $n\in\{k+1,k+2,\ldots,N\}$. We have shown that $h(n)=p_{v}(n)$ for all $n\in\{0,1,\ldots,N\}$, and the question is positively answered for $N=q^{k}+k,k\geq 1$.