Dominant Segment Split

You are given a string S consisting of lowercase English letters.

A segment (substring) is called dominant if:

• One character appears more than half of the segment’s length.

Your task is to:

• Split the string into maximum number of contiguous segments

• Each segment must be dominant

Return the maximum number of such segments.

📥 Input Format

• A single string S

📤 Output Format

• An integer representing the maximum number of dominant segments

⚙️ Constraints

• 1≤∣S∣≤1051 \le |S| \le 10^51≤∣S∣≤105

• String contains only lowercase English letters (a–z)

🧪 Example

Input:

aaabbcaaa

Output:

3

Explanation: Possible split → aaa | bb | caaa

• "aaa" → dominant (a = 3/3)

• "bb" → dominant (b = 2/2)

• "caaa" → dominant (a = 3/4)