Chef and String

 

Problem Summary

You have N students in a row, each either a girl ('x') or a boy ('y').
Students are friends only with their immediate neighbors (left/right).

Rules for forming pairs:

• Each pair must be exactly one boy and one girl.

• Only adjacent students (friends) can form a pair.

• Each student can be in at most one pair.

For each test case (string S of length N), you must find the maximum number of pairs that can be formed.

Input:

• T test cases.

• For each test case: a string S of 'x' and 'y'.

Output:

• For each test case: one integer — the maximum number of valid pairs.

Constraints:

• 1 ≤ T ≤ 100

• 1 ≤ N ≤ 105

• Total sum of N over all test cases ≤ 3×105

• S contains only 'x' and 'y'.

Examples Explanation

Sample:

Input:

3

xy

xyxxy

yy

Output:

1

2

0

• Case 1: "xy"

• Only pair: (1, 2) = 'x' & 'y' → 1 pair.

• Case 2: "xyxxy"

• One valid configuration: (1,2) and (4,5).

• Another valid configuration: (2,3) and (4,5).

• In both, maximum pairs = 2.

• Case 3: "yy"

• Two boys, no girl → no boy-girl pair → 0.

Approach

Pattern:

This is a straightforward greedy + single pass string processing problem.

Naive Idea:

Consider all possible edges (i, i+1) and try to pick some non-overlapping subset of boy-girl edges using complex matching algorithms.

But:

• Here the graph is just a simple line.

• Each node can be in at most one pair.

• We only need adjacent opposite-gender pairs.

So a very simple greedy algorithm works in linear time.

Optimal Greedy Approach

High-level idea:

Walk from left to right:

• Whenever you see two consecutive students with opposite genders ("xy" or "yx"), form a pair and skip both.

• Otherwise, just move one step right.

This is optimal because:

• Any pair must be adjacent; we never skip a valid edge that would help later, because using it cannot block a better future edge (at most it shifts the side by 1, but the unpaired neighbor remains available).

• It's equivalent to finding a maximum matching in a path graph where edges are between consecutive indices that are 'x'-'y' or 'y'-'x'. The simple greedy of taking the earliest available edge is optimal for paths.

Detailed logic:

• Let i = 0.

• While i < N - 1:

• If S[i] != S[i+1], they are opposite genders:

• Make a pair → pairs++.

• Skip both: i += 2.

• Else:

• No pair from (i, i+1), move on: i += 1.

Edge cases:

• N = 1: no neighbors → answer is 0.

• All same characters (xxxx or yyyy): no adjacent opposite pair → 0.

Pseudo-code

Complexity Analysis:

Let total length over all test cases be Ntotal.

• Each test case: one linear scan, at most N iterations.

• Time Complexity: O(Ntotal)

• Space Complexity: O(1) (aside from storing the input string).

Java code

C code

C++ code

Python code

JavaScript code