Cycle String?#12802

Cycle String? (Editorial)

Author:

Anton Trygub

Developer:

Nazarii Denha

Editorialist:

Stanislav Bezkorovainyi

Let's say, that cnt_{ch} is the number of occurrences of character in the string. Let's say that is such a character, that cnt_{cm} is maximum among all cnt_{ch}.

Now, there are several possible scenarios.

Scenario 1. cnt_{cm} = 2 \cdot n. In other words, the string consists of the same characters. Obviously, the answer in that case is "NO".

Scenario 2. cnt_{cm} = 2 \cdot n - 1 and n \geq 2. In other words, the string consists of the same characters, except for one position. The answer in that case is "NO".

Proof. Let's say that "a" and the only symbol not equal to is equal to "c". Our string will look like this:

aaaaaaaaaa\ldots aaaaacaaaaa \ldots aaaaaaaaaa

Since the string is cyclical, then cyclical shiftings of the string do not change it. Let's shift it the way that the only character that differs from the rest is placed on the right side of the string. Now the string looks like this:

\rlap{$\overbrace{\phantom{aaaaaa\ldots aaaaaa}}^{n \ characters}$}a \underbrace{aaaaa\ldots aaaaaaa}_{n \ characters}aaaa\ldots aaaaac

Scenario 3. cnt_{cm} = 2 \cdot n - 2, n \geq 3 and the characters besides are the same. The answer in that case is "NO".

Proof. Let's say that "a" and the rest of the characters are equal to "c". Now we shift the string with cyclic shifts in such a way that the first character of the sting is "c". Let's denote the other position on the string, where character "c" is placed as . Now, our string looks like this:

\overbrace{caaaaa\ldots aaac}^{p \ characters}aaa\ldots aaaaaa

It is obvious that p-2 < n+1. Otherwise, there would have been at least two strings of length containing only characters "a" between and . For similar reason 2 \cdot n - p < n+1.

p-2 < n + 1 \Longleftrightarrow p < n + 3
2\cdot n - p < n + 1 \Longleftrightarrow n - p < 1 \Longleftrightarrow p > n - 1

Now we know that is either equal to or n+1 or n+2.

Why not ? The substring is equal to concatenation of string g_1 and g_2 (remember, our string is cyclical, so everything is fine):

\underbrace{ca}_{g_2} \overbrace{aaaa\ldots aaaca}^{t} \underbrace{aaaaaa\ldots aaaaaa}_{g_1 = n-2 \textrm{\ same symbols}}

Why not n+1? The substring is equal to substring :

\overbrace{caaaaa\ldots aaa}^{t} \overbrace{caaaaa\ldots aaa}^{g}

Why not n+2? We can make n+1 cyclic shifts to left and after that we'll get the same situation as when p=n.

So there is no valid way to place , so the answer is "NO".

Scenario 4. cnt_{cm} = 2 \cdot n - 2, n \geq 3 and the characters besides are distinct. In this case the answer is "YES".

Proof + the way to build such string. Let's say that "a" and the other two characters are equal to "c" and "d". We can build the answer this way:

\overbrace{caaa\ldots aaa}^{n \ \textrm{symbols}} \overbrace{daaa\ldots aaa}^{n \ \textrm{symbols}}

It is obvious that every substring will contain either "c" or "d" but not both of them. Since there is only one character "c", any two different substrings that contain "c" will have it on different positions and thus will be distinct. The same goes for any two substrings that contain "d".

Scenario 5. cnt_{cm} \leq n. In this case the answer is "YES".

Proof + the way to build such string. We can simply sort the string.

Let's suppose that it does not work and there are two identical substrings s_i and s_j of length that start on positions and respectively, where i < j. Let's denote the first character of s_j as . Let's say that at the beginning of the string s_j there are p \leq n characters . Since s_i = s_j same should go for s_i. If character at position j+p-1 is equal to too, then, since the string is sorted, there are at least j+p-i > p characters at the beginning of the string s_i. We face contradiction and thus, the statement is false, i.e there are indeed no same substrings that start on different positions.

Scenario 6. n < cnt_{cm} \leq 2 \cdot n - 3. In this case the answer is "YES".

Proof + the way to build such string. Let's say that "a" and the rest of the symbols are "b", "c", "d", , "z". We can put an arbitrary symbol besides on the first position, then symbols (let's call it block_1), then all the remaining symbols besides in any order (let's call it block_2), then cnt_{cm} - n symbols (let's call it block_3):

b\overbrace{aaaaaaaaaaa\ldots aaaaaaaaaaa}^{block_1 \textrm{~--- } n \ \textrm{symbols $cm$}} \overbrace{zbtbcydcceecgy\ldots vwqxheyqyui}^{block_2 \textrm{~--- } \textrm{the rest of the symbols}}\overbrace{aaaaaaaaaaa\ldots aaaaaaaaaaa}^{block_3 \textrm{~--- } cnt_{cm}-n \ \textrm{symbols $cm$}}

We should notice, that since cnt_{cm} \leq 2 \cdot n - 3 \Longleftrightarrow cnt_{cm} - n \leq n - 3. And thus length of block_3 is smaller than n-2.

Why all of the substrings of length will be unique?

  • Substring that starts on position is the only substring that starts from a symbol that is not equal to and is followed by n-1 characters .

  • Substring that starts on position is the only substring that consists only of characters .

  • Substring that starts on position is the only substring that has n-1 symbols at the beginning and one symbol that is not equal to in the end.

  • Substrings that start on positions from to n+1 are the only substrings that start from and they have a substring of length that consists of characters that are not equal to . They will differ among themselves because they all have different number of -s at their beginning.

  • Substrings that start on positions in block_2 are the only substrings that start from symbol that is not equal to and have \leq n-2 characters in them. They will differ among themselves because lengths of their prefixes that do not contain symbol are distinct.

  • Substrings that start from positions in block_3 are the only substrings that start with symbol and have a symbol surrounded by -s that is not equal to (I'm talking about the first character of the string). They will differ among themselves by positions of the character that is not equal to .