C++: Độ dài chuỗi hướng robot rút gọn (R/U → D)

Bài toán: Chuỗi S chỉ chứa 'R' (phải) và 'U' (lên). Cặp "RU" hoặc "UR" → gộp thành 'D' (chéo). Tìm độ dài chuỗi sau rút gọn tối đa.

Thuật toán: Duyệt trái sang phải. Nếu S[i] != S[i+1] → gộp cặp này, bỏ qua i+1, đếm +1. Ngược lại đếm +1 cho S[i].

Code C++

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

int solve(string S) {
    int ans = 0;
    for (int i = 0; i < (int)S.size(); i++) {
        if (i + 1 < (int)S.size() && S[i] != S[i+1]) {
            i++; // bo qua ky tu tiep theo da gop
        }
        ans++;
    }
    return ans;
}

int main() {
    cout << solve("RUURU") << endl; // 3 (RU→D, U, RU→D → "DUD")
    return 0;
}

Kết quả

3