[Solution] Crazy Subsequences solution codechef

Crazy Subsequences solution codechef – Chef has a binary string S. He can modify it by choosing any subsequence of length 3 from it and deleting the first and last character of the subsequence.

[Solution] Crazy Subsequences solution codechef

For example, if S = \textcolor{red}{11}01\textcolor{red}{0}1, Chef can choose the subsequence marked in red and delete its first and last characters, obtaining the string S = 1011.

Chef wonders what is the lexicographically largest string he can obtain by modifying the original string using a finite number of operations. Please help Chef in this task.

Note: A binary string A is said to be lexicographically larger than another binary string B if:

• B is a proper prefix of A (for example, 101 is lexicographically larger than 10); or
• There exists an index i such that A_1 = B_1, A_2 = B_2, \ldots, A_{i-1} = B_{i-1} and A_i \gt B_i.

Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of a single line of input containing the original binary string S.

Output Format

For each test case, output on a new line the lexicographically largest string Chef can obtain.

Crazy Subsequences solution codechef

• 1 \leq T \leq 2\cdot 10^4
• 3 \leq |S| \leq 10^5
• S is a binary string, i.e, only contains the characters 0 and 1 in it
• The sum of |S| over all test cases won’t exceed 3\cdot 10^5.

Sample 1:

Input

Output

4
101
1010
0000
0001

101
11
0000
01


Crazy Subsequences solution codechef Explanation:

Test case 1: It is optimal to not perform any moves.

Test case 2: In one move, by choosing the subsequence 1\textcolor{red}{010}, the string can be made into 11, which is the lexicographically largest possible.

Test case 3: It is optimal to not perform any move.