Guidewire

01Minimum Boys Next to Girls

You are given a row of seats represented by a string s.

'G' means the seat is already occupied by a girl.
'-' means the seat is empty, and you may place a boy there. Place the minimum number of boys so that every girl has at least one adjacent boy immediately to her left or right. Boys can only be placed in empty seats. Return the minimum number of boys required. If it is impossible to satisfy every girl, return -1.

Constraints

1 ≤ s.length ≤ 2 * 10⁵
s[i] is either 'G' or '-'.
Adjacency only means immediate left or immediate right.

Example 1

Input:

s = "-G-GG--"

Output:

Explanation: One optimal placement is -GBGGB- with boys at indices 2 and 5.

Example 2

Input:

s = "G-G"

Output:

Explanation: Placing one boy in the middle seat covers both girls.

Example 3

Input:

s = "G"

Output:

-1

解法

贪心扫一遍：先把整串按「极大 G 段」分块，每个 G 段长度 L 需要 L/2 个相邻男生(典型「每两个 G 至少夹一个 B」)，但还要看左右是否有空位放男生。若某个 G 段被孤立(两端都不是 - 且段长 ≥ 2 无法满足)，返回 -1；单个 G 而两侧都没空位也是 -1。线性扫描 O(n)，空间 O(1)。

def minBoysNextToGirls(s: str) -> int:
    n = len(s)
    arr = list(s)
    boys = 0
    i = 0
    while i < n:
        if arr[i] == 'G':
            j = i
            while j < n and arr[j] == 'G':
                j += 1
            # G segment [i, j-1]
            left_empty = i > 0 and arr[i - 1] == '-'
            right_empty = j < n and arr[j] == '-'
            seg_len = j - i
            if seg_len == 1:
                if left_empty:
                    arr[i - 1] = 'B'
                    boys += 1
                elif right_empty:
                    arr[j] = 'B'
                    boys += 1
                else:
                    return -1
            else:
                # Need a boy between every pair of adjacent G, but here all chars are G.
                # The only way: a boy must be on one side. With only one side adjacency,
                # an internal G in a contiguous G run cannot be covered. So len >= 2
                # is feasible only if seg can be split by placing boys at both ends.
                if seg_len > 2:
                    return -1
                if left_empty and right_empty:
                    arr[i - 1] = 'B'; arr[j] = 'B'; boys += 2
                elif left_empty:
                    arr[i - 1] = 'B'; boys += 1
                    # still need to check second G covered: it has G on left, must be -1
                    return -1
                elif right_empty:
                    arr[j] = 'B'; boys += 1
                    return -1
                else:
                    return -1
            i = j
        else:
            i += 1
    return boys

class Solution {
    int minBoysNextToGirls(String s) {
        int n = s.length();
        char[] a = s.toCharArray();
        int boys = 0, i = 0;
        while (i < n) {
            if (a[i] == 'G') {
                int j = i;
                while (j < n && a[j] == 'G') j++;
                boolean leftEmpty = i > 0 && a[i - 1] == '-';
                boolean rightEmpty = j < n && a[j] == '-';
                int len = j - i;
                if (len == 1) {
                    if (leftEmpty) { a[i - 1] = 'B'; boys++; }
                    else if (rightEmpty) { a[j] = 'B'; boys++; }
                    else return -1;
                } else if (len == 2) {
                    if (leftEmpty && rightEmpty) { a[i - 1] = 'B'; a[j] = 'B'; boys += 2; }
                    else return -1;
                } else {
                    return -1;
                }
                i = j;
            } else i++;
        }
        return boys;
    }
}

#include <string>

class Solution {
public:
    int minBoysNextToGirls(std::string s) {
        int n = s.size(), boys = 0, i = 0;
        while (i < n) {
            if (s[i] == 'G') {
                int j = i;
                while (j < n && s[j] == 'G') j++;
                bool leftEmpty = i > 0 && s[i - 1] == '-';
                bool rightEmpty = j < n && s[j] == '-';
                int len = j - i;
                if (len == 1) {
                    if (leftEmpty) { s[i - 1] = 'B'; boys++; }
                    else if (rightEmpty) { s[j] = 'B'; boys++; }
                    else return -1;
                } else if (len == 2) {
                    if (leftEmpty && rightEmpty) { s[i - 1] = 'B'; s[j] = 'B'; boys += 2; }
                    else return -1;
                } else return -1;
                i = j;
            } else i++;
        }
        return boys;
    }
};