ปัญหา
สตริงสมดุล (Balanced String) คือสตริงที่มีจำนวน 'L' และ 'R' เท่ากัน กำหนดสตริงสมดุล s แบ่งเป็นสตริงสมดุลย่อยได้มากที่สุด คืนจำนวนสูงสุด เช่น "RLRRLLRLRL" → 4 ("RL", "RRLL", "RL", "RL")
วิธีแก้
- cnt = 0, ans = 0
- ลูป i = 0 ถึง n-1:
- cnt = 0
- ลูป j = i ถึง n-1:
- ถ้า s[j]=='R' cnt++ ไม่งั้น cnt--
- ถ้า j-i>0 และ cnt==0: ans++, i=j, break
- คืน ans
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int balancedStringSplit(string s) {
int cnt = 0, ans = 0;
for (int i = 0; i < s.size(); i++) {
cnt = 0;
for (int j = i; j < s.size(); j++) {
if (s[j] == 'R') cnt++;
else cnt--;
if (j - i > 0 && cnt == 0) {
ans++; i = j; break;
}
}
}
return ans;
}
};
int main() {
Solution ob;
cout << ob.balancedStringSplit("RLLLLRRRLR");
}
อินพุต
"RLLLLRRRLR"
เอาต์พุต
3
คำอธิบาย
"RLLLLRRRLR" → แบ่งได้ 3 ส่วน: "RL", "LLRR", "RLR" (หรือ "RL", "LLRR", "RL", "R" - ตัวสุดท้ายไม่สมดุล)
อัลกอริทึม Greedy: ทุกครั้งที่ cnt กลายเป็น 0 (สมดุล) ตัดทันที จะได้จำนวนสูงสุด
เวอร์ชันที่ดีกว่า: Single Pass O(n) แค่นับ balance++/-- ทุกครั้ง balance==0 ans++
