All Tracks Algorithms String Algorithms Basics of String Manipulation Problem

Unique subsequences
/

Algorithms, Arrays, String Manipulation, String manipulation

Problem
Editorial
Analytics

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

\(1 \le T \le 10^3\\ 1 \le N \le 10^5\)

Note: The sum of \(N\) overall test cases do not exceed \(10^6\).

SAMPLE INPUT
2
5
ababa
5
aaaac

SAMPLE OUTPUT
5
2

Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?