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