สมมติว่าเรามีสตริงที่อักขระแต่ละตัวเป็น "L", "R" หรือ "?" "L" หมายถึงย้ายหน่วยไปทางซ้ายหนึ่งหน่วย "R" หมายถึงย้ายหน่วยไปทางขวาหนึ่งหน่วยและ "?" หมายถึง "L" หรือ "R" ถ้าเราอยู่ที่ตำแหน่ง 0 เราต้องหาระยะทางสูงสุดที่เป็นไปได้จาก 0 โดยแทนที่ "?" ด้วย "L" หรือ "R"
ดังนั้น หากอินพุตเป็นแบบ "LLRRL หรือไม่" ผลลัพธ์จะเป็น 3 ให้แทนที่ ? ใช้ L เพื่อเลื่อนไปทางซ้าย 5 หน่วยและไปทางขวา 2 หน่วย ดังนั้นการกระจัดสูงสุดคือ 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
op :=0, l :=0, r :=0
-
สำหรับแต่ละมันใน s -
-
ถ้ามันเหมือนกับ 'L' แล้ว −
-
(เพิ่ม l ขึ้น 1)
-
-
มิฉะนั้นเมื่อมันเหมือนกับ 'R' แล้ว −
-
(เพิ่ม r ขึ้น 1)
-
-
มิฉะนั้น
-
(เพิ่ม op โดย 1)
-
-
-
ผลตอบแทนสูงสุดของ (l และ r) - ขั้นต่ำของ (l และ r) + op
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(string s) {
int op = 0;
int l = 0;
int r = 0;
for (auto &it : s) {
if (it == 'L') {
l++;
} else if (it == 'R') {
r++;
} else {
op++;
}
}
return max(l, r) - min(l, r) + op;
}
};
main() {
Solution ob;
cout << (ob.solve("LLRRL??"));
} อินพุต
"LLRRL??"
ผลลัพธ์
3
