Last Updated: 7 Mar, 2021
Split Concatenated String
Moderate
Asked in companies
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.
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
Approaches
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