Prefix Removals (Codeforces 1654B)
Tags: Others, 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: 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: 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.

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". 

Sample Inputs:
6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw

Sample Outputs:
abdc
a
b
deforces
cf
xyzzw

Solution (Python):
def i():
    s = input()
    c = {}
    for x in s:
        if x in c:
            c[x] += 1
        else:
            c[x] = 1
    p = 0
    for x in s:
        if c[x] == 1:
            return s[p:]
        else:
            c[x] -= 1
        p += 1
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
    return list(map(typ, stdin.readline().split()))

def rv(typ):
    return map(typ, stdin.readline().split())

def main():
    for _ in range(inp()):
        d = dd(int)
        s = rs()
        for i in s:
            d[i] += 1
        for i in range(len(s)):
            if d[s[i]] == 1:
                x = i
                break
            d[s[i]] -= 1
        print(s[x:])
main()

Solution (Python):
t = int(input())
for _ in range(t):
    s = input()
    p = {c: i for (i, c) in enumerate(s)}
    res = s[min(p.values()):]
    print(res)