# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* vlad_c

*satyam_343*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1396

# PREREQUISITES:

Sets, maps, or similar data structures

# PROBLEM:

You’re given the order in which N programs are opened (or reopened).

Each time a program is (re)opened, it moves to the front of the list.

Find the final order of programs; print the last 2 characters of each one.

# EXPLANATION:

Let S_i denote the i-th input string.

Instead of looking at the process in forward order, let’s look at it in reverse order.

- Clearly, S_N is the last program opened, which means it’ll be in the front of the list.
- S_{N-1} is the penultimate program opened.

If it doesn’t equal S_N, we know it’s the second program in the list; otherwise it equals S_N and was already processed. - Similarly, if S_{N-2} equals either S_N or S_{N-1}, then it would’ve been processed already.

Otherwise, it’s the next program in the list. - More generally, for any 1 \leq i \leq N,
- If S_i equals one of S_{i+1}, S_{i+2}, \ldots, S_N, then it was already processed ‘later’.
- Otherwise, it’s the next program in the list since everything in front of it was taken care of.

This gives us a straightforward algorithm:

- For each i from N down to 1, check if S_i equals one of S_{i+1}, S_{i+2}, \ldots, S_N, i.e, if it was seen before.

To do this quickly, the simplest way is to maintain a set or map of strings, each time inserting S_i into it.

This can be implemented with, for example,`std::set<string>`

or`std::unordered_set<string>`

in C++,`set`

in Python, or`HashSet`

in Java. - If has occurred earlier, ignore it. Otherwise, print its last two characters.

# TIME COMPLEXITY

\mathcal{O}(N) set/map operations per testcase.

# CODE:

## Author's code (C++)

```
///(sol_stl.cpp) Expected: AC.
#include <bits/stdc++.h>
#define maxs 45
using namespace std;
char s[maxs+5];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n;
stack<string> stk;
string s;
while (n--) {
cin >> s; stk.push(s);
}
set<string> ss;
while (!stk.empty()) {
if (!ss.count(stk.top())) {
cout << stk.top().substr(stk.top().size() - 2, 2);
ss.insert(stk.top());
}
stk.pop();
}
return 0;
}
```

## Editorialist's code (Python)

```
n = int(input())
names = []
for i in range(n):
names.append(input())
seen = set()
ans = ''
for i in reversed(range(n)):
if names[i] in seen: continue
ans += names[i][-2]
ans += names[i][-1]
seen.add(names[i])
print(ans)
```