Page Contents
Minimum Longest Substring Codechef Solution
You are given a binary string A of length N. Rearrange the binary string to form binary strings S and T such that the length of the longest common substring between S and T is minimum.
Print both strings S and T.
Note that both S and T must be anagrams of A — see the examples below for more clarity.
Input Format
The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
Each test case consists of two lines.
The first line of each test case contains a single integer N — the length of the binary string A.
The second line of each test case contains a binary string A of length N.
Output Format
For each test case, output two lines. The first line contains string S while the second line contains string T. Both strings S and T must be anagrams of string A and thus, have length N.
Constraints
1≤T≤1000
1≤N≤1000
Sum of N over all cases does not exceed 3000.
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 1: The given string is A=101. Two rearrangements of A such that the length of longest common substring is minimum are S=110 and T=011. The longest common substring between strings S and T is 11, having length 2. It can be proved that for no other pair of rearrangements of string A, the LCS has a length less than 2.
Test case 2: The given string is A=1111. Here, all rearrangements of A are the same. Two rearrangements of A such that the length of longest common substring is minimum are S=1111 and T=1111. The longest common substring between strings S and T is 1111, having length 4.
Test case 3: The given string is A=0111. Two rearrangements of A such that the length of longest common substring is minimum are S=1101 and T=0111. The longest common substring between strings S and T is 01 having length 2. It can be proved that for no other pair of rearrangements of string A, the LCS has a length less than 2.
SOLUTION
Program: Minimum Longest Substring Codechef Solution in Python
for test in range(int(input())): n = int(input()) s = input() o = s.count('1') z = s.count('0') if o==0 or z==0: print(s) print(s) elif o > z: p = '' c = 0 ans = 1 equal = o//(z+1) ext = o%(z+1) while c < z: p += '1'*equal if ext: p+='1' ext-=ans p += '0' c += ans p += '1' * equal print('0' * z + '1' * o) print(p) elif z>o: p = '' c = 0 ans = 1 equal = z // (o + 1) ext = z % (o + 1) while c < o: p += '0' * equal if ext: p += '0' ext -= ans p += '1' c += ans p += '0' * equal print('1' * o + '0' * z) print(p) else: p = '10'*(n//2) print('0' * z + '1' * o) print(p)
Program: Minimum Longest Substring Codechef Solution in C++
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int tcase, cnt[2], n, flag; char str[1005]; cin >> tcase; while(tcase --) { memset(cnt, 0, sizeof(cnt)); cin >> n >> str; for(int i = 0; i < n; i ++) cnt[str[i] - '0'] ++; flag = (cnt[0] <= cnt[1]); sort(cnt, cnt + 2); for(int i = 0; i < cnt[0]; i ++) cout << 1 - flag; for(int i = 0; i < cnt[1]; i ++) cout << flag; cout << '\n'; for(int i = 0; i <= cnt[0]; i ++) { for(int j = 0; j < cnt[1] / (cnt[0] + 1); j ++) cout << flag; if(i < (cnt[1] % (cnt[0] + 1))) cout << flag; if(i != cnt[0]) cout << 1 - flag; } cout << '\n'; } }
Program: Minimum Longest Substring Codechef Solution in Java
/* package codechef; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Codechef { public static void main (String[] args) throws java.lang.Exception { // your code goes here Scanner scan = new Scanner(System.in); short t = scan.nextShort(); while(t-->0){ short n = scan.nextShort(); String a = scan.next(); char[] chArr = a.toCharArray(); short n0 = 0; for(char ch : chArr){ if(ch=='0') n0++; } if(n%2==0&&n0 == n/2){ for(int i =0;i<n/2;i++ ){ System.out.print('0'); } for(int i =0;i<n/2;i++ ){ System.out.print('1'); } System.out.println(""); for(int i = 0;i<n;i++){ if(i%2==0){ System.out.print('1'); }else{ System.out.print('0'); } } System.out.println(""); continue; } int m = Math.min(n0,n-n0); int M = n-m; char chMin = m==n0 ? '0':'1'; char chMax = m==n0 ? '1':'0'; for(int i =0;i<n;i++){ chArr[i]=chMax; } int l = M/(m+1); int r = M%(m+1); int c = r==0? 0:1; int k=l+c; while(k<n){ chArr[k] =chMin; if(c<r){ k=k+1; c++; } k = k+l+1; } for(int j=0;j<m;j++){ System.out.print(chMin); } for(int j=0;j<M;j++){ System.out.print(chMax); } System.out.println(""); System.out.println(String.valueOf(chArr)); } } }
Related:
- Perfect Imperfections 2 Codechef Solution
- Kostomuksha and AESC MSU Codechef Solution
- Minimum Longest Substring Codechef Solution
- Same Parity Swaps in Binary Strings Codechef Solution
- Missing Numbers Codechef Solution
- The Rating Dilemma Codechef Solution
- Chef and Races Codechef Solution
- The Three Topics Codechef Solution
- Increase IQ Codechef Solution