New update is available. Click here to update.

Last Updated: 11 Mar, 2021

Difficulty: Moderate

```
The string is ‘RR’, ‘RB’ so we can combine ‘RR’ and ‘RB’ as the last character of ‘RR’ i.e ‘R’ matches with the first character of ‘RB’. But we cant combine ‘RB’ and ‘RR’ as the last character of ‘RB’ i.e ‘B’ doesn't matches with the first character of ‘RR’ i.e ‘R’ so our answer is '4'.
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains an integer ‘N’ denoting the number of strings.
The second line of each test case contains ‘N’ space-separated strings.
```

```
For each test case, print a single line containing a single integer denoting the maximum length of string which can be formed. In case no two strings can add simply print ‘0’.
The output of each test case will be printed in a separate line.
```

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
2 <= N <= 1000
1 <= | ST | <= 1000
Where ‘T’ represents the number of test cases and ‘N’ represents the total number of strings and '|ST|' represents the length of each of the ‘N’ strings.
Time Limit: 1 second
```

- We have to find out all the possible permutations by satisfying the given condition. For this, we make another helper function that also takes into count the index. So starting from the first index of our vector we have to go to the last index.
- So for checking all the permutations, we run a loop that swaps the element of the vector array so we get all the possible permutations and for every permutation, we check how many maximum elements are satisfying our required condition that the last character of the first element is equal to the last character of the second element.
- So for checking with every index we call a recursive function and store the max so that we are able to get our maximum value after every recursive function.
- Hence at last we simply return our maximum count as an answer.

We have to find out the maximum length of string which can be formed by joining two strings if the first character of the first string is equal to the last character of the second string.

- So for this, we think of the possible pair as our string only contains characters ‘R’ and ‘B’. So for this, we define four variables ‘RR’ which counts the number of string which has ‘R’ as its first character and ‘R’ as its last character, ‘RB’ which counts the number of string which has ‘R’ as its first character and ‘B’ as its last character, ‘BR’ which counts the number of string which has ‘B’ as its first character and ‘R’ as its last character, ‘BB’ which counts the number of string which has ‘B’ as its first character and ‘B’ as its last character.

- If the count of ‘BR’ and ‘RB’ is ‘0’
- Our answer is simply the maximum of the count of ‘RR’ and ‘BB’ multiplied by the length of the string. As for string which is starting from ‘R’ and ending with ‘R’ can’t be combined with the strings which are starting from ‘B’ and ending with ‘B’ or vice versa they can just add into himself like ‘BBB+BBB’ or ‘RRR’ + ‘RRR’ so we check the count whether the count of ‘RR’ is greater or ‘BB’ is greater.
- Hence returns the maximum’ of ( count of ‘RR’ and count of ‘BB’).

- Else if the count of ‘RB’ and ‘BR’ is not ‘0’ then two conditions occur:
- If the count of ‘RB’ and ‘BR’ is equal we simply add all four variables as we are now able to combine all the strings as if we add a string with ‘RR’ orientation now we can use a string with ‘RB’ orientation and then ‘BB’ orientation or if we use ‘BB’ orientation first then we can use ‘BR’ orientation and then ‘RR’ so we can add all the four strings.

- Else if the count of ‘RB’ and ‘BR’ is not equal we can’t add our four strings we can only add ‘RR’ and ‘BB’ string types if we have ‘BR’ and ‘RB’ strings so we can only able to add them the minimum from ‘BR’ and ‘RB’ times so our answer would be ‘RR’+’BB’+min(‘BR’+’RB’)+1.

SIMILAR PROBLEMS

Divisible Substrings

Posted: 29 Jul, 2022

Difficulty: Easy

Ninja and Numbers

Posted: 30 Jul, 2022

Difficulty: Moderate

Longest Palindromic Substring

Posted: 4 Sep, 2022

Difficulty: Moderate

Cakes

Posted: 23 Sep, 2022

Difficulty: Easy

1-3 Palindrome

Posted: 4 Oct, 2022

Difficulty: Easy

Popular Interview Problems: