You are given a string \(S\) that contains \(N\) characters. Your task is to determine the maximum possible size of the subsequence \(T\) of \(S\) such that no two adjacent characters in \(T\) are the same.
Note: The string contains only lowercase English alphabets.
Input format
- First line: A single integer \(T\) denoting the number of test cases
- For each test case:
- First line: Single integer \(N\) denoting the size of the string
- Second line: \(S\) denoting the string
Output format
For each test case, print a single line containing one integer that represents the maximum size of the subsequence that satisfies the provided condition.
Constraints
Note: The sum of \(N\) overall test cases do not exceed \(10^6\).
2 5 ababa 5 aaaac
5 2
For the string \(ababa\) we can select the complete string as \(T\), since no two adjacent characters are identical, so answer is \(5\).
For the string \(aaaac\) the maximum possible \(T\) which can be formed is \(ac\) so answer is 2.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor