Brain Power

시간 제한1초메모리 제한1024 MB

요약
소문자 문자열을 이웃한 조각끼리 애너그램이 되지 않도록 최대 개수의 비어 있지 않은 조각으로 나눈다.
난이도

보통10점 중 6점

유형
그리디, 해시맵, 문자열, 구현
정답자
아직 제출이 없습니다

문제

You are given a string ss consisting of lowercase English letters. Your task is to split ss into a sequence of non-empty substrings such that no two adjacent substrings in the sequence are anagrams of each other. (Two strings are considered anagrams if they contain the same characters with the same frequencies.) Among all such valid splits, you must maximize the number of substrings.

입력

The first line of the input contains a single integer TT, the number of test cases.

The following TT lines each describe a test case. Each line contains a single string ss consisting of lowercase English letters.

출력

For each test case, print a single integer on a new line: the maximum possible number of substrings in a valid split.

제한

  • 1≤T≤1051 \le T \le 10^5
  • 1≤∣s∣≤1051 \le |s| \le 10^5 for each test case.
  • The total length of all strings ss over all test cases does not exceed 10510^5.

예제3

  1. 예제 1

    입력
    5
kaist
rrunnn
iiccppcc
mooockk
connttest
    예상 출력
    5
4
6
5
8

  2. 예제 2

    입력
    8
a
bb
ccc
dddd
eeeee
ffffff
ggggggg
hhhhhhhh
    예상 출력
    1
1
2
3
3
4
5
5

  3. 예제 3

    입력
    4
brainpowerletthebasskick
oooooooooooaaaaeaaiau
joooooooooooooaaeoaauua
eeeeeeeeeaaaaeaeiea
    예상 출력
    22
15
17
15