Branches of Bytecode

Last Updated on March 28, 2022 by Ria Pathak

Concepts Used

String

Difficulty Level

Hard

Problem Statement (Simplified):

For given n strings and a separator s, print n/2 number of strings of equal length, by concatenating two substrings with separator. Print the lexicographically smaller strings first. Every string formed must be printed exactly once ( See Test case for explanation ).

See original problem statement here

Test Case

Input:
1
4
d
cc
jv
e
5

Output:
cc5d
e5jv

Explanation:
Here we have to create 2 strings of equal length with given concatenating character (5) from given 4 strings, so possible cases are:

cc5d
d5cc
d5jv
jv5d
cc5e
e5cc
e5jv
jv5e

But we have to print lexicographically smaller strings, so we print 'cc5d' and 'e5jv'.

Solving Approach :

Bruteforce Approach:

1) We can calculate all possible strings of 2 strings from given strings. After finding all possible strings, we print the lexicographically smaller strings.
2) We can form a total ^{n}C_{2} strings, where n is the number of given strings. Hence, this takes O(n²) time to find all strings. Comparing all strings to find lexicographically smaller strings takes another O(n³) time. Hence, the total time complexity of the given approach is O(n³) which is very inefficient for the larger number of strings. Hence we try for a new efficient approach.

Efficient Approach:

1) We can solve this problem if we sort all the strings, so that concatenation gives lexicographically smaller strings.
2) We add the separator to the end of all string, which can be removed later.
3) For n/2 strings to print, the total length of a string must be the sum of the length of all strings with n/2 in addition as there would be n/2 separators in between, divided by n/2 as sum gives total characters in answer, but we need the length of 1 string.
4) We check for all combinations of strings, and concatenate them, one string with length equal to the required length string is our valid string, so we print and remove the last character as that is a separator which is not needed.
5) We remove these two strings so that they are not repeated again.

Example

• Lets take strings discussed in test case section, we have "d", "cc", "jv" and "e". Also we have to print N/2 i.e. 4/2 => 2 strings of equal size.

• We concatenate the concatenating character at end of each string. This makes all strings as "d5", "cc5", "jv5" and "e5".

• Now we sort all the strings lexicographically making array of strings as ["cc5","d5","e5","jv5"].

• Now we have sorted them in asked order, we can concatenate strings such that their total length becomes the required length i.e. 5 in our case.

For string "cc5" :

• Second string = "d5", as their total size is 5, so we print them as one and drop the last character from second string. Also, we make them null so that they can’t be used again. We print "cc5d".
• Our final array of strings becomes ["","","e5","jv5"].

For string "e5" :

• Second string = "jv5", as their total size is 5, so we print them as one and drop the last character from second string. Also, we make them null so that they can’t be used again. We print "e5jv".

• Our final array of strings becomes ["","","",""].

• As our whole array is used. We terminate the program. For a better reference, you can watch the following video.

Youtube Video

BYTECODE Solution (Youtube)

Solutions

#include <stdio.h>
#include<string.h>

int main()
{
  int test;
  scanf("%d",&test);

  while(test--){

    int n;
    scanf("%d",&n);

    char a[n][99999];
    for(int i=0; i<n; i++)
      scanf("%s",a[i]);

    char seperator[2];
    scanf("%s",seperator);

    int total_len = 0;
    for(int i=0; i<n; i++){
      strcat(a[i],seperator);
      total_len += strlen(a[i]);
    }

    total_len = total_len/(n/2);
    for(int i=0; i<n; i++)
      for(int j=i+1; j<n; j++)
        if(strcmp(a[i],a[j])>0){
          char temp[99999];
          strcpy(temp,a[i]);
          strcpy(a[i],a[j]);
          strcpy(a[j],temp);
        }

    for(int i=0; i<n; i++)
      for(int j=i+1; j<n; j++){
        if(strlen(a[i])+strlen(a[j]) == total_len){
          printf("%s",a[i]);
          int len = strlen(a[j]);
          a[j][len-1] = '\0';
          printf("%s\n",a[j]);
          a[i][0] = '\0';
          a[j][0] = '\0'; 
        }
      }

  }
}

#include<bits/stdc++.h>
using namespace std;

int main(){
  int test;
  cin>>test;

  while(test--){

    int n;
    cin>>n;

    char a[n][99999];
    for(int i=0; i<n; i++)
      cin>>a[i];

    char seperator[2];
    cin>>seperator;

    int total_len = 0;
    for(int i=0; i<n; i++){
      strcat(a[i],seperator);
      total_len += strlen(a[i]);
    }

    total_len = total_len/(n/2);
    for(int i=0; i<n; i++)
      for(int j=i+1; j<n; j++)
        if(strcmp(a[i],a[j])>0){
          char temp[99999];
          strcpy(temp,a[i]);
          strcpy(a[i],a[j]);
          strcpy(a[j],temp);
        }

    for(int i=0; i<n; i++)
      for(int j=i+1; j<n; j++){
        if(strlen(a[i])+strlen(a[j]) == total_len){
          cout<<a[i];
          int len = strlen(a[j]);
          a[j][len-1] = '\0';
          cout<<a[j]<<endl;
          a[i][0] = '\0';
          a[j][0] = '\0'; 
        }
      }

  }
}

import java.util.*;
import java.io.*;

public class Main{
  public static void main(String args[]) throws IOException{

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test-->0){

      int n = sc.nextInt();

      String a = new String[n];
      for(int i=0; i<n; i++)
        a[i] = sc.next();

      String seperator = sc.next();

      int total_len = 0;
      for(int i=0; i<n; i++){
        a[i] += seperator;
        total_len += a[i].length();
      }

      total_len = total_len/(n/2);
      for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
          if(a[i].compareTo(a[j])>0){
            String temp = a[i];
            a[i] = a[j];
            a[j] = temp;
          }

      for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++){
          if(a[i].length()+a[j].length() == total_len){
            System.out.println(a[i]+a[j].substring(0,a[j].length()-1));
            a[i] = "";
            a[j] = ""; 
          }
        }

    }
  }
}

This article tried to discuss String. Hope this blog helps you understand and solve the problem. To practice more problems on String you can check out MYCODE | Competitive Programming.