Question
Maximum Substring Split
You are given a string S of length N. Your task is to split this string into as many substrings as possible such that the concatenation of all the substrings results in the original string S. Additionally, for each substring Ai (where 1 < i ≤ K), it must not be equal to its previous substring Ai-1.
Find the maximum number K of substrings that can be created while satisfying these conditions.
Input
The first line of the input contains a single integer N.
The second line of the input contains a string S of length N.
Constraints
1 ≤ N ≤ 104
S contains lower case alphabets.
The second line of the input contains a string S of length N.
Constraints
1 ≤ N ≤ 104
S contains lower case alphabets.
Output
Print the maximum such integer K which satisfies the above conditions.
Example
Sample Input
xxyyxx
Sample Output
4
Explanation
We can divide this string into: xx, y, yx, x
xxyyxx
Sample Output
4
Explanation
We can divide this string into: xx, y, yx, x