A NOTE ON THE NUMBER OF SQUARESIN A PARTIAL WORD WITH ONE HOLE

A well known result of Fraenkel and Simpson states thatthe number of distinct squares in a word of length n is bounded by2n since at each position there are at most two distinct squares whoselast occurrence starts. In this paper, we investigate squares in partialwords with one hole, or sequences over a finite alphabet that have a“do not know” symbol or “hole”. A square in a partial word overa given alphabet has the form uv where u is compatible with v, andconsequently, such square is compatible with a number of words overthe alphabet that are squares. Recently, it was shown that for partialwords with one hole, there may be more than two squares that havetheir last occurrence starting at the same position. Here, we prove thatif such is the case, then the length of the shortest square is at most halfthe length of the third shortest square. As a result, we show that thenumber of distinct squares compatible with factors of a partial wordwith one hole of length n is bounded by 7n2