T533480 「GFOI Round 2」Abstract String Basic (English ver.)
题目背景
**[Chinese statement](https://www.luogu.com.cn/problem/P11279). You must submit your code at the Chinese version of the statement.**
题目描述
Charlie is taking a course called *Basics of Abstract Strings*.
> **Definition 3.1:** For two lowercase strings $S$ and $T$ of the same length, their **similarity** is defined as the number of matching characters in corresponding positions. Formally, if $|S| = |T| = n$, then the similarity between $S$ and $T$ is given by $\psi(S, T) = \sum\limits_{i=1}^n \sum\limits_{j=1}^n [i = j][S_i = T_j]$.
>
> **Lemma 3.1:** For any lowercase string $S$, there exists a unique lowercase string $T$ that maximizes $\psi(S, T)$.
>
> **Proof of Lemma 3.1:** ...
Charlie’s mind begins to wander, and he starts scribbling aimlessly on his paper. Suddenly, he comes up with a new idea: what if he defines the **dissimilarity** between $S$ and $T$ as the number of pairs where both the position and the character are different? Formally, this similarity can be defined as $\tilde{\psi}(S, T) = \sum\limits_{i=1}^n \sum\limits_{j=1}^n [i \neq j][S_i \neq T_j]$. This whimsical definition snaps Charlie out of his daydream. Now, he wonders: what kind of lowercase string $T$ would maximize the dissimilarity between $S$ and $T$?
**Note:** The square brackets $[x]$ represent Iverson brackets, which evaluate to $1$ if the condition $x$ is true, and $0$ otherwise.
输入格式
无
输出格式
无
说明/提示
#### Sample $1$ Explanation
When $T = \texttt{godfather}$, $\tilde{\psi}(S, T) = 72$, reaching the maximum value. Note that there may be more than one valid answer.
#### Subtasks and Constraints
| Subtask ID |$n\le$ | Special Properties | Score |
| :-----------: | :-----------: |:----:|:----:|
|$0$ |$28$ | Tests are samples | $0$ |
|$1$ |$4$ | No |$20$ |
|$2$ |$10^6$ | $S$ doesn't contain the character `z` |$20$ |
|$3$ |$10^3$ | No |$20$ |
|$4$ |$10^6$ | No |$40$ |
For all tests, it is guaranteed that:
- $1 \le n \le 10^6$;
- $S$ consists only of lowercase letters.