Split a String in Balanced Strings

Muvozanatlashgan satr (balanced string) shunday satrki, unda 'L' va 'R' belgilarining soni bir xil.

Sizga muvozanatlashgan s satri berilgan. Uni shunday qilib qism-satrlarga bo'lingki:

Har bir qism-satr o'z-o'zidan muvozanatlashgan bo'lsin.
Qism-satrlar soni imkon qadar maksimal bo'lsin.

Olinishi mumkin bo'lgan maksimal muvozanatlashgan qism-satrlar sonini qaytaring.

example.go

func solve(s string) int {
    // ...
}

Misollar

kod

Input: s = "RLRRLLRLRL"
Output: 4
Tushuntirish: s ni quyidagi qismlarga bo'lish mumkin: "RL", "RRLL", "RL", "RL". Ularning har birida L va R lar soni teng.

kod

Input: s = "RLRRRLLRLL"
Output: 2

kod

Input: s = "LLLLRRRR"
Output: 1

Maslahatlar

Har safar L va R sonlari tenglashganda, ochko'zlik (greedy) bilan darhol bitta muvozanatli bo'lakni "kesib olish" mumkinligini o'ylang.
Satrni chapdan o'ngga aylanib, L uchun balansni oshiring, R uchun kamaytiring; balans nolga tushgan har safar hisoblagichni oshiring — bu eng maksimal bo'linish soni bo'ladi.

OldingiKeyingi