## Codeforces Round #778 – Problem B

B. Prefix Removals

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

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

The first line contains a single integer t (1≤t≤104) — 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⋅105 inclusive.

It is guaranteed that the sum of the lengths of s over all test cases does not exceed 2⋅105.

## Output

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.

## Example input

```
6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw
```

## Example output

```
abdc
a
b
deforces
cf
xyzzw
```

## 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”.

## Solution

#include <iostream> #include <map> #include <vector> #include <string> using namespace std; int main(){ int t; cin >> t; while (t--) { string a; cin >> a; int n = a.size(); map<char, int> d; // store the index of last appearance of a[i] for (int i=0;i<n;i++) { d[ a[i] ] = i; } int i; for (i=0;i<n;i++) { // stop when there's no a[i] after index i if (d[ a[i] ] <= i) break; } // print the rest of the string from that position for (;i<n;i++) { cout << a[i]; } cout << endl; } return 0; }