Erase First or Second Letter
Contest: Codeforces Round 917 (Div. 2)
Difficulty rating: 1100
Tags: brute force, combinatorics, data structures, dp, strings

You are given a string $$$s$$$ of length $$$n$$$. Let's define two operations you can apply on the string:

- remove the first character of the string;
- remove the second character of the string.

Your task is to find the number of distinct non-empty strings that can be generated by applying the given operations on the initial string any number of times (possibly zero), in any order.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the string.

The second line of each test case contains the string $$$s$$$. It is guaranteed that the string only contains lowercase letters of the English alphabet.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer: the number of distinct non-empty strings you can get.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can get the following strings: $$$a$$$, $$$aa$$$, $$$aaa$$$, $$$aaaa$$$, $$$aaaaa$$$.

In the third test case, for example, the word $$$ba$$$ can be reached in the following way:

- remove the first character of the current string $$$ababa$$$, getting $$$baba$$$;
- remove the second character of the current string $$$baba$$$, getting $$$bba$$$;
- remove the second character of the current string $$$bba$$$, getting $$$ba$$$.

Example input:
5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst

Example output:
5
1
9
50
210

Editorial:
Hint $$$1$$$: Do we need to use the first operation after the second operation?
Hint $$$2$$$: Try to fix the number of the applied first operation. How many different strings can be obtained?
Hint $$$3$$$: When can two reached strings be the same?
Hint $$$4$$$: Try to consider the first occurrence for each letter.
Editorial:
Let's first see, that applying the second operation and then the first is equivalent to applying the first operation twice. In the former case the string will become $$$s_1s_2s_3 \ldots s_n \to s_1s_3 \ldots s_n \to s_3 \ldots s_n$$$, and in the latter case: $$$s_1s_2s_3 \ldots s_n \to s_2s_3 \ldots s_n \to s_3 \ldots s_n$$$. As we are concerned with only the number of distinct resulting strings, let's assume that the second operation is never done before the first operation. This means we do $$$op_1$$$ first operations (possibly zero) and then $$$op_2$$$ second operations (possibly zero).
Let's now find the result of applying $$$i$$$ of the first and then $$$j$$$ of the second operations. It's easy to see, that the result is $$$s_{i+1}s_{i+j+2}s_{i+j+3} \ldots s_n$$$.
The only remaining question is in which cases two sequences of operations such that the first operation always comes before the second result in the same string. Consider for the $$$(i_1, j_1)$$$ pair, the resulting string is the same as for the $$$(i_2, j_2)$$$ pair. We can see that $$$i_1+j_1 = i_2+j_2$$$, because the number of erased letters should be the same to get strings of the same length. Next, $$$s_{i_1+1} = s_{i_2+1}$$$ as those are the first letters of two resulting equal strings. It's easy to see that these conditions are also sufficient for the result to be the same string.
If after applying the first operation $$$op_1$$$ times the first letter is not its first occurrence, then any subsequent result could have been achieved by less operations of the first type by removing first character until reaching that letter and then by removing the second character until we reach $$$op_1$$$ operations in total. This means we need to consider using the second operation only at the first occurrence of the letter.
The final solution can look like this: for each letter $$$a \ldots z$$$ find it's first occurrence. If the letter is found, any number of second type operations lead to a different result. Thus we can just calculate the number of second operations that is valid and add that to the answer.