Split Concatenated String

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
12 upvotes
Asked in companies
Amazonalibaba

Problem statement

You are given ‘N’ strings. You could concatenate these strings into one where for each string you could reverse it or not. Among all the possible strings you need to find a lexicographically largest string by cutting and making one point in any part of the string which will make the looped string into a regular one starting from the breakpoint character.

String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y|, if either |x| > |y| and x1 = y1, x2 = y2, ..., x|y| = y|y|, or exists such number r (r < |x|, r < |y|), that x1 = y1, x2 = y2, ..., xr = yr and xr + 1 > yr + 1.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2T’ lines represent the ‘T’ test cases. 

The first line of each test case contains one integers ‘N’ denoting the number of strings.

The second line contains N space-separated strings.
Output Format : 
For each test case print the lexicographically biggest string.
Constraints : 
1 <= T <= 50
1 <= N <= 100
1 <= length of string(si) <= 100  for all  1 <= i < = n 

Time Limit: 1sec
Sample Input 1 :
2
2
abc def
1
aab
Sample Output 1 :
fedcba
baa
Explanation For Sample Input 1 :
In the first case
The possible strings after looping:-
-abcdef-, -abcfed-, -cbadef-, -cbafed-, where - represents the loop.
From 4th string =cbafed
On cutting the string about f
fed+cba=fedcba
The lexicographically biggest possible string is fedcba.

In the second case
The possible strings are:-
aab baa
The lexicographically biggest possible string is baa.

Sample Input 2 :

2
3
aaa ccc ddd
2
azy bom

Sample Output 2 :

dddaaaccc
zamoby
Hint

For all strings from i = 1 to n if str[i] < reverse(str[i]).Then replace str[i] by reverse(str[i]).

Approaches (1)
Brute Force

The key idea is to first check for all strings that if str[i]<reverse(str[i]) then replace str[i] by reverse(str[i]).After this split the concatenated string about all the  character of the string.

 

Algorithm :

 

  • First check for all strings that if str[i] <reverse(str[i]) then replace str[i] by reverse(str[i]).
  • After iterating through all strings and for all strings iterate through its characters.
  • For the jth character of string spit about this point.After splitting the given string will be temp=((j to len -1) characters of ith string) +( i+1 to n strings)+(0 to i-1 strings).
  • If the temp is greater than ans then ans=temp
  • In the end, return the ans string
Time Complexity

O(N * MAX(L)), where 'N' is the total number of strings and 'L' is the length of the longest string in the array.

 

For every ith string we are reversing it which takes O(len(str[i]) time .Then we are concatenating for every ith step temp=((j to len(length of ith string) ) characters of ith string) +( i+1 to n strings)+(0 to i-1 strings) .Which takes O(len(str[i]) time.

 

Hence total time complexity is O(n * max(len(str[i])) + n * max(len(str[i]))). => O(max(len(str[i])))

Space Complexity

O(N) Where N is the total number of strings

 

We are storing the n strings in a single variable temp. Hence space complexity is O(N).

Code Solution
(100% EXP penalty)
Split Concatenated String
Full screen
Console