Friend Groups In A Line solution codechef
' denotes, there is a person standing in the ' position.
The distance between two people standing in theand positions respectively in the queue is , where denotes the absolute value of . Now, two people are considered to be friends if they are at a distance less than or equal to .
Let’s say, there arepeople, standing one after another in a queue such that for each , and are friends, then all the people are considered to be in a friend group.
For example, consider the string
" and " .
Let’s denote the people standing in the, , and positions in the queue by respectively. Now, and are friends as the distance between them is , and are also friends as the distance between them is . is not friend with anyone. Hence form a friend group and forms a separate friend group.
Now each person can move one position right or one position left or stay in the same position. However, they can’t move out of the queue. Find the minimum number of friend groups they can form if they move optimally.
It is possible that there is more than one person standing in the same position after the movements.
Input Format Friend Groups In A Line solution codechef
- The first line of 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 integers .
- The second line of each test case contains a string .
Output Format Friend Groups In A Line solution codechef
For each test case, print a single line containing one integer – the minimum number of friend groups.
Constraints Friend Groups In A Line solution codechef
- contains only characters ‘ ` and ‘ ‘
- The sum of over all test cases does not exceed .
Sample Input 1
3 6 2 010010 4 0 1001 7 2 1101001
Sample Output 1
1 2 1
Test case: If the person standing in the position moves one position left, the distance between the two people becomes which is equal to . So they form a friend group.
Test case: If the person standing in the position moves one position right and the person standing in the position moves one position left, the string becomes “ “, still the distance between them is greater than . So they form two separate friend groups.
Test case: Initially first three people form a friend group and the fourth person forms a separate friend group. Now if the fourth person moves one position left, he becomes a friend of the third person as the distance between these two people is equal to , and hence all the four people belong to one friend group.
Solution: Click here