Minimum Longest Substring Codechef Solution

by

Table of 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:

Leave a Comment

6 − 6 =