Minimum Longest Substring Codechef Solution | MARCH CHALLENGE

Codechef
Share:

Minimum Longest Substring Codechef Solution

You are given a binary string AA of length NN. Rearrange the binary string to form binary strings SS and TT such that the length of the longest common substring between SS and TT is minimum.

Print both strings SS and TT.

Note that both SS and TT must be anagrams of AA — see the examples below for more clarity.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of two lines.
  • The first line of each test case contains a single integer NN — the length of the binary string AA.
  • The second line of each test case contains a binary string AA of length NN.

Output Format

  • For each test case, output two lines. The first line contains string SS while the second line contains string TT. Both strings SS and TT must be anagrams of string AA and thus, have length NN.

Constraints

  • 1≤T≤10001≤T≤1000
  • 1≤N≤10001≤N≤1000
  • Sum of NN over all cases does not exceed 30003000.

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

3
3
101
4
1111
4
0111

Sample Output 1 

110
011
1111
1111
1101
0111

Explanation

Test case 11: The given string is A=101A=101. Two rearrangements of AA such that the length of longest common substring is minimum are S=110S=110 and T=011T=011. The longest common substring between strings SS and TT is 1111, having length 22. It can be proved that for no other pair of rearrangements of string AA, the LCS has a length less than 22.

Test case 22: The given string is A=1111A=1111. Here, all rearrangements of AA are the same. Two rearrangements of AA such that the length of longest common substring is minimum are S=1111S=1111 and T=1111T=1111. The longest common substring between strings SS and TT is 11111111, having length 44.

Test case 33: The given string is A=0111A=0111. Two rearrangements of AA such that the length of longest common substring is minimum are S=1101S=1101 and T=0111T=0111. The longest common substring between strings SS and TT is 0101 having length 22. It can be proved that for no other pair of rearrangements of string AA, the LCS has a length less than 22.

Minimum Longest Substring Codechef  SOLUTION

Download Code

Read More Post Here

Leave a Comment

Your email address will not be published. Required fields are marked *

x