Manipulating History (Codeforces 1688C)
Tags: Greedy, strings

As a human, she can erase history of its entirety. As a Bai Ze (Hakutaku), she can create history out of nothingness.—Perfect Memento in Strict SenseKeine has the ability to manipulate history. The history of Gensokyo is a string $$$s$$$ of length $$$1$$$ initially. To fix the chaos caused by Yukari, she needs to do the following operations $$$n$$$ times, for the $$$i$$$-th time:  She chooses a non-empty substring $$$t_{2i-1}$$$ of $$$s$$$. She replaces $$$t_{2i-1}$$$ with a non-empty string, $$$t_{2i}$$$. Note that the lengths of strings $$$t_{2i-1}$$$ and $$$t_{2i}$$$ can be different.Note that if $$$t_{2i-1}$$$ occurs more than once in $$$s$$$, exactly one of them will be replaced.For example, let $$$s=$$$"marisa", $$$t_{2i-1}=$$$"a", and $$$t_{2i}=$$$"z". After the operation, $$$s$$$ becomes "mzrisa" or "marisz".After $$$n$$$ operations, Keine got the final string and an operation sequence $$$t$$$ of length $$$2n$$$. Just as Keine thinks she has finished, Yukari appears again and shuffles the order of $$$t$$$. Worse still, Keine forgets the initial history. Help Keine find the initial history of Gensokyo!Recall that a substring is a sequence of consecutive characters of the string. For example, for string "abc" its substrings are: "ab", "c", "bc" and some others. But the following strings are not its substring: "ac", "cba", "acb".HacksYou cannot make hacks in this problem.

Input: Each test contains multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^3$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n < 10 ^ 5$$$) — the number of operations.The next $$$2n$$$ lines contains one non-empty string $$$t_{i}$$$ — the $$$i$$$-th string of the shuffled sequence $$$t$$$.The next line contains one non-empty string $$$s$$$ — the final string.It is guaranteed that the total length of given strings (including $$$t_i$$$ and $$$s$$$) over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$. All given strings consist of lowercase English letters only.It is guaranteed that the initial string exists. It can be shown that the initial string is unique.

Output: For each test case, print the initial string in one line.

Note: Test case 1:Initially $$$s$$$ is "a". In the first operation, Keine chooses "a", and replaces it with "ab". $$$s$$$ becomes "ab". In the second operation, Keine chooses "b", and replaces it with "cd". $$$s$$$ becomes "acd".So the final string is "acd", and $$$t=[$$$"a", "ab", "b", "cd"$$$]$$$ before being shuffled.Test case 2:Initially $$$s$$$ is "z". In the first operation, Keine chooses "z", and replaces it with "aa". $$$s$$$ becomes "aa". In the second operation, Keine chooses "a", and replaces it with "ran". $$$s$$$ becomes "aran". In the third operation, Keine chooses "a", and replaces it with "yakumo". $$$s$$$ becomes "yakumoran".So the final string is "yakumoran", and $$$t=[$$$"z", "aa", "a", "ran", "a", "yakumo"$$$]$$$ before being shuffled.

Sample Inputs:
2
2
a
ab
b
cd
acd
3
z
a
a
aa
yakumo
ran
yakumoran

Sample Outputs:
a
z

Solution (Python):
from sys import stdin
input = stdin.readline

def ii():
    return int(input())

def li():
    return list(map(int, input().split()))
for _ in range(ii()):
    n = ii()
    l_t = []
    for i in range(2 * n):
        t = input().strip()
        l_t.append(t)
    s = input().strip()
    st = ''.join(l_t) + s
    ans = ''
    for i in range(ord('a'), ord('z') + 1):
        ch = chr(i)
        if st.count(ch) % 2:
            ans = ch
            break
    print(ans)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = ''.join((input() for _ in range(2 * n + 1)))
    for ch in s:
        if s.count(ch) % 2:
            print(ch)
            break

Solution (Python):
import io
import os
from collections import Counter

def read_nums():
    return [int(x) for x in input().split()]

def read_line():
    return input().decode().strip()

def solve():
    (n,) = read_nums()
    tokens = []
    for _ in range(2 * n):
        tokens.append(read_line())
    tokens = Counter(tokens)
    final = read_line()
    letter_counts = Counter()
    for (token, count) in tokens.items():
        for ch in token:
            letter_counts[ch] += count
    for ch in final:
        letter_counts[ch] += 1
    for ch in set([t for t in tokens if len(t) == 1]):
        if letter_counts[ch] % 2 == 1:
            return ch
    raise RuntimeError()

def main():
    (t,) = read_nums()
    for _ in range(t):
        print(solve())
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    main()