สมมติว่าเรามีสตริง S ที่มีตัวอักษร n ตัว ตัวอักษรเป็น 'R' หรือ 'U' บนเครื่องบิน 2 มิติ หุ่นยนต์สามารถไปทางขวาหรือขึ้นได้ เมื่อเป็น 'R' มันจะเลื่อนไปทางขวา และเมื่อเป็น 'U' มันจะเลื่อนขึ้น อย่างไรก็ตาม สตริงมีขนาดใหญ่เกินไป เราต้องการทำให้สตริงมีขนาดเล็กลง คู่เช่น "RU" หรือ "UR" จะถูกแทนที่ด้วยการเคลื่อนที่แนวทแยง "D" เราต้องหาความยาวของสตริงรีดิวซ์ที่อัปเดตครั้งสุดท้าย
ดังนั้น หากอินพุตเป็น S ="RUURU" ผลลัพธ์จะเป็น 5 เพราะสตริงจะเป็น "DUD"
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ans := 0 n := size of S for initialize i := 0, when i < n, update (increase i by 1), do: if S[i] is not equal to S[i + 1], then: (increase i by 1) (increase ans by 1) return ans
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
int solve(string S){
int ans = 0;
int n = S.size();
for (int i = 0; i < n; ++i){
if (S[i] != S[i + 1])
i++;
ans++;
}
return ans;
}
int main(){
string S = "RUURU";
cout << solve(S) << endl;
} อินพุต
"RUURU"
ผลลัพธ์
3
