Header Ads Widget

Summary Power | Codechef solution

You work as an engineer. You were given an empty board with  consecutive cells; at any moment, each cell can display one character.

You want the board to display a string  with length >. Since the board isn't large enough, you want to display the string in +1 steps. In the -th step (1+1), you'll make the board display the characters ,+1,,+1.

The power required to switch the board from step  to step +1 (for 1) is equal to the number of characters displayed on the board that have to change between these steps. You should find the total power required for the whole process of displaying a string, i.e. the sum of powers required for switching between all consecutive pairs of steps.

Input

  • The first line of the input contains a single integer  denoting the number of test cases. The description of  test cases follows.
  • The first line of each test case contains two space-separated integers  and .
  • The second line contains a single string  with length .

Output

For each test case, print a single line containing one integer — the total power required for text switching.

Constraints

  • 11,000
  • 2105
  • 1<
  • each character of  is a lowercase English letter
  • the sum of  for all test cases does not exceed 106

Subtasks

Subtask #1 (20 points):

  • 1100
  • 250

Subtask #2 (80 points): original constraints

Sample 1:

Input
Output
3
6 3
aabbcc
5 2
abccc
4 3
aabb
4
3
1

Explanation:

Example case 1:

  • In step 1, the board is displaying "aab".
  • In step 2, the board is displaying "abb".
  • In step 3, the board is displaying "bbc".
  • In step 4, the board is displaying "bcc".

The power required for switching from the 1-st to the 2-nd step is 1, because cell 1 changes from 'a' to 'a' (requiring power 0), cell 2 changes from 'a' to 'b' (requiring power 1) and cell 3 changes from 'b' to 'b' (requiring power 0); 0+1+0=1.

The power required for switching between the 2-nd and 3-rd step is 2 and the power required for switching between the 3-rd and 4-th step is 1.

Therefore, the answer is 1+2+1=4.

 Code(C++):-


Code(JAVA):-

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-