[Solution] String protocol solution codechef

String protocol solution codechef – An input string SS of length NN is transferred through the network using a special protocol. The protocol can send the string through a series of operations. In one operation, we can choose a lowercase english alphabet CC and do one of the following:

  • Transfer 11 copy of CC through the network.
  • Transfer 22 copies of CC through the network.

String protocol solution codechef

Each of the above transfers take 11 unit of time.

Find the minimum time in which we can transfer the entire string SS through the network.

Input Format

  • The first line will contain TT – the number of test cases. Then the test cases follow.
  • First line of each test case contains NN – the length of the string SS.
  • Second line of each test case contains the string SS.

Output Format

For each test case, output in a single line, the minimum time required to transfer the string.

String protocol solution codechef

  • 1T1001≤T≤100
  • 1N1051≤N≤105
  • Sum of NN over all test cases does not exceed 105105.
  • String SS contains lowercase english alphabets only.

Sample Input 1 

2
5
cbcdc
6
aabeee

String protocol solution codechef

 

5
4

String protocol solution Explanation

Test Case 11: String can be transferred through following operations: send 11 copy of character 𝚌c, send 11 copy of character 𝚋b, send 11 copy of character 𝚌c, send 11 copy of character 𝚍d, and send 11 copy of character 𝚌c. Thus, total 55 operations are required.

Test Case 22: String can be transferred through following operations: send 22 copies of character 𝚊a, send 11 copy of character 𝚋b, send 11 copy of character 𝚎e, and send 22 copies of character 𝚎e. Thus, total 44 operations are required.

For Solution

Click Here

Leave a Comment