Prefix Removals
Contest: Технокубок 2022 - Финал
Difficulty rating: 800
Tags: strings

You are given a string $$$s$$$ consisting of lowercase letters of the English alphabet. You must perform the following algorithm on $$$s$$$:

- Let $$$x$$$ be the length of the longest prefix of $$$s$$$ which occurs somewhere else in $$$s$$$ as a contiguous substring (the other occurrence may also intersect the prefix). If $$$x = 0$$$, break. Otherwise, remove the first $$$x$$$ characters of $$$s$$$, and repeat.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".

For instance, if we perform the algorithm on $$$s =$$$ "abcabdc",

- Initially, "ab" is the longest prefix that also appears somewhere else as a substring in $$$s$$$, so $$$s =$$$ "cabdc" after $$$1$$$ operation.
- Then, "c" is the longest prefix that also appears somewhere else as a substring in $$$s$$$, so $$$s =$$$ "abdc" after $$$2$$$ operations.
- Now $$$x=0$$$ (because there are no non-empty prefixes of "abdc" that also appear somewhere else as a substring in $$$s$$$), so the algorithm terminates.

Find the final state of the string after performing the algorithm.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

This is followed by $$$t$$$ lines, each containing a description of one test case. Each line contains a string $$$s$$$. The given strings consist only of lowercase letters of the English alphabet and have lengths between $$$1$$$ and $$$2 \cdot 10^5$$$ inclusive.

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

Output format:
For each test case, print a single line containing the string $$$s$$$ after executing the algorithm. It can be shown that such string is non-empty.

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

Note:
The first test case is explained in the statement.

In the second test case, no operations can be performed on $$$s$$$.

In the third test case,

- Initially, $$$s =$$$ "bbbbbbbbbb".
- After $$$1$$$ operation, $$$s =$$$ "b".

In the fourth test case,

- Initially, $$$s =$$$ "codeforces".
- After $$$1$$$ operation, $$$s =$$$ "odeforces".
- After $$$2$$$ operations, $$$s =$$$ "deforces".

Example input:
6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw

Example output:
abdc
a
b
deforces
cf
xyzzw

Editorial:
Let a be the initial string. For a string z, let's define z(l,r)=zlzl+1...zr, i.e., the substring of z from l to r. The final string is a(k,n) for some k
.
In the final string, x=0 , so the first character doesn't appear anywhere else in s. This means that ak+1,ak+2,...,an≠ak. In other words, ak is the rightmost occurrence of a letter in s
.
Can you ever remove ai , if ai+1,ai+2,...,an≠ai? Notice that you would need to remove a(l,r) (l≤i≤r): this means that there must exist a(l',r')=a(l,r) for some l'>r. So, ai+l'−l=ai
, and this is a contradiction.
Therefore, k is the smallest index such that ak+1,ak+2,...,an≠ak
.
You can find k by iterating over the string from right to left and updating the frequency of each letter. ai+1,ai+2,...,an≠ai if the frequency of the letter ai is 0. k is the minimum such i
.
Complexity: O(n)