A - Dividing a String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300300 点

問題文

英小文字からなる文字列 SS が与えられます。以下の条件をみたす最大の正整数 KK を求めてください。

  • SS の空でない KK 個の文字列への分割 S=S1S2...SKS=S_1S_2...S_K であって Si≠Si+1S_i \neq S_{i+1} (1≦i≦K−11 ≦ i ≦ K-1) を満たすものが存在する。

ただし、S1,S2,...,SKS_1,S_2,...,S_K をこの順に連結して得られる文字列のことを S1S2...SKS_1S_2...S_K によって表しています。

制約

  • 1≦∣S∣≦2×1051 ≦ |S| ≦ 2 \times 10^5
  • SS は英小文字からなる

入力

入力は以下の形式で標準入力から与えられる。

SS

出力

条件をみたす最大の正整数 KK を出力せよ。

入力例 1Copy

Copy
aabbaa

出力例 1Copy

Copy
4

例えば aa,b,ba,a と SS を 44 つの文字列に分割することができます。

入力例 2Copy

Copy
aaaccacabaababc

出力例 2Copy

Copy
12

Score : 300300 points

Problem Statement

Given is a string SS consisting of lowercase English letters. Find the maximum positive integer KK that satisfies the following condition:

  • There exists a partition of SS into KK non-empty strings S=S1S2...SKS=S_1S_2...S_K such that Si≠Si+1S_i \neq S_{i+1} (1≤i≤K−11 \leq i \leq K-1).

Here S1S2...SKS_1S_2...S_K represents the concatenation of S1,S2,...,SKS_1,S_2,...,S_K in this order.

Constraints

  • 1≤∣S∣≤2×1051 \leq |S| \leq 2 \times 10^5
  • SS consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

SS

Output

Print the maximum positive integer KK that satisfies the condition.

Sample Input 1Copy

Copy
aabbaa

Sample Output 1Copy

Copy
4

We can, for example, divide SS into four strings aa, b, ba, and a.

Sample Input 2Copy

Copy
aaaccacabaababc

Sample Output 2Copy

Copy
12

2025-04-15 (Tue)
12:45:01 +00:00