หาเวลาที่สัญญาณครอบคลุม String ทั้งหมด (x และ o) ใน C++

โจทย์: String ประกอบ 'x' (source) และ 'o' (target) สัญญาณจาก 'x' แพร่ทั้ง 2 ทิศ ทุก 1 unit time แปลง 'o' 1 ตัว หาเวลาที่ string ทั้งหมดกลายเป็น 'x'

ตัวอย่าง: "xooxoooxxoooxoooxooxooox" → 2

อัลกอริธึม: หา longest stretch ของ 'o' ระหว่าง 'x'

Stretch อยู่ระหว่าง 2 'x' → เวลา = ceil(len / 2) (แพร่จากทั้งสองข้าง)
Stretch อยู่ปลาย (มี 'x' แค่ข้างเดียว) → เวลา = len
คำตอบ = max เวลาของทุก stretch

ตัวอย่างโค้ด C++

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

int findMaximumDuration(string s, int n) {
    int right = 0, left = 0;
    int count = 0, maxLen = INT_MIN;
    s += '1'; // sentinel
    for (int i = 0; i <= n; i++) {
        if (s[i] == 'o') count++;
        else {
            if (count > maxLen) {
                right = 0; left = 0;
                if (s[i] == 'x') right = 1;
                if (i - count > 0 && s[i - count - 1] == 'x') left = 1;
                count = ceil((double)count / (right + left));
                maxLen = max(maxLen, count);
            }
            count = 0;
        }
    }
    return maxLen;
}

int main() {
    string str = "xooxoooxxoooxoooxooxooox";
    cout << findMaximumDuration(str, str.size());
}

อินพุต

xooxoooxxoooxoooxooxooox

เอาต์พุท

Complexity

Time: O(N)
Space: O(1)