Tính thời gian tín hiệu lan truyền đến mọi vị trí trong chuỗi C++

Chuỗi chứa 'x' (nguồn tín hiệu) và 'o'. Tín hiệu lan 2 chiều, 1 đơn vị thời gian chuyển 1 'o' thành 'x'. Tìm thời gian để toàn bộ chuỗi thành 'x'.

Ví dụ

"xooxoooxxoooxoooxooxooox" → Output: 2

Thuật toán

• Tìm các đoạn 'o' liên tiếp giữa hai 'x' (hoặc đầu/cuối).
• Đoạn giữa 2 'x': thời gian = ceil(len / 2).
• Đoạn đầu/cuối chỉ có 1 'x' bên cạnh: thời gian = len.
• Kết quả = max của các đoạn.

Code C++

#include <bits/stdc++.h>
using namespace std;

int maxTime(string s) {
    s += 'x'; // sentinel
    int n = s.size(), maxT = 0, cnt = 0;
    bool leftX = false;
    
    for (int i = 0; i < n; i++) {
        if (s[i] == 'o') cnt++;
        else { // s[i] == 'x'
            if (cnt > 0) {
                int t = leftX ? (cnt + 1) / 2 : cnt; // ceil(cnt/2) nếu 2 bên, else cnt
                maxT = max(maxT, t);
                cnt = 0;
            }
            leftX = true;
        }
    }
    return maxT;
}

int main() {
    cout << maxTime("xooxoooxxoooxoooxooxooox"); // 2
    return 0;
}

Kết quả

2

Độ phức tạp: O(n) thời gian, O(1) không gian.