{"id":1176,"date":"2020-06-10T14:27:47","date_gmt":"2020-06-10T14:27:47","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1176"},"modified":"2022-03-28T00:56:24","modified_gmt":"2022-03-28T00:56:24","slug":"branches-of-bytecode","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/branches-of-bytecode\/","title":{"rendered":"Branches of Bytecode"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

String<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

For given n<\/code> strings and a separator s<\/code>, print n\/2<\/code> 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 ).<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\n1\n4\nd\ncc\njv\ne\n5\n\nOutput:\ncc5d\ne5jv\n\nExplanation:\nHere we have to create 2 strings of equal length with given concatenating character (5) from given 4 strings, so possible cases are:\n\ncc5d\nd5cc\nd5jv\njv5d\ncc5e\ne5cc\ne5jv\njv5e\n\nBut we have to print lexicographically smaller strings, so we print 'cc5d' and 'e5jv'.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
\n
1) We can calculate all possible strings of 2 strings from given strings. After finding all possible strings, we print the lexicographically smaller strings.
\n2) We can form a total ^{n}C_{2}<\/code> strings, where n<\/code> is the number of given strings. Hence, this takes O(n2<\/sup>) time to find all strings. Comparing all strings to find lexicographically smaller strings takes another O(n3<\/sup>) time. Hence, the total time complexity of the given approach is O(n3<\/sup>) which is very inefficient for the larger number of strings. Hence we try for a new efficient approach.<\/p>\n<\/blockquote>\n
Efficient Approach:<\/h4>\n
\n
1) We can solve this problem if we sort all the strings, so that concatenation gives lexicographically smaller strings.
\n2) We add the separator to the end of all string, which can be removed later.
\n3) For n\/2<\/code> strings to print, the total length of a string must be the sum of the length of all strings with n\/2<\/code> in addition as there would be n\/2 separators in between, divided by n\/2<\/code> as sum gives total characters in answer, but we need the length of 1 string.
\n4) 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.
\n5) We remove these two strings so that they are not repeated again.<\/p>\n<\/blockquote>\n
Example<\/h3>\n
\n