สำหรับโจทย์ข้อนี้ หากทดลองเลือกทั้งหมด ${n \choose 2}$ ช่วงที่เป็นไปได้พร้อมนับจำนวน "อ้า" กับ "โอ้" จะต้องใช้เวลามากถึง $O(n^2)$ ซึ่งไม่ทันสำหรับกรณีที่ $n$ มีค่ามากถึง $1\,000\,000$

หากเรากำหนดให้คำว่า "โอ้" (O) มีค่าเท่ากับ $+1$ และคำว่า "อ้า" (R) มีค่าเท่ากับ $-k$ จะสังเกตได้ว่า ช่วงที่มีคำว่า "โอ้" เป็นจำนวน $k$ เท่าของจำนวนคำว่า "อ้า" ที่เราต้องการนั้นจะหาผลรวมได้เท่ากับ $0$ พอดี

ถ้าเรานิยาม Prefix Sum $qs(i) = \sum\limits_{j=1}^{i} A_i$ โดย $A_i$ คือค่าของคำที่ $i$ ตามนิยามข้างต้น โจทย์ของเราจะเป็นการหาช่วง $(j, i]$ ($0 \leq j < i \leq n$) ที่สมการ

$qs(i)-qs(j) = 0$

เป็นจริง และทำให้ค่า $i-j$ (ความยาวของช่วง) มากที่สุดที่เป็นไปได้

ดังนั้น เราสามารถใช้ขั้นตอนวิธีดังต่อไปนี้ในการแก้โจทย์

• สร้าง map หรือ unordered_map ขึ้นมาเพื่อให้ เมื่อกำหนดค่า $x$ ใด ๆ จะหาค่า $j$ ที่น้อยที่สุดที่ทำให้ $qs(j)=x$ ได้อย่างรวดเร็ว
• ไล่ $i=1,2,3,\dots,n$ โดยนำค่า $i$ ไปเก็บใน map/unordered_map ถ้าไม่เคยเจอ prefix sum เท่ากับ $qs(i)$ มาก่อน แต่ถ้าเคยเจอแล้ว ให้ตรวจสอบว่าค่า $j$ ที่น้อยที่สุดคืออะไร แล้วเก็บคำตอบ $i-j$ (ความยาวของช่วง) ที่มากที่สุดไว้

Time Complexity: $O(n \log n)$ หรือ $O(n)$ เมื่อใช้ map หรือ unordered_map ตามลำดับ

Space Complexity: $O(n)$

Implementation

ในภาษา C++:

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

typedef long long ll;
const int N = 1e6 + 10;

int n, k;
char s[N];
unordered_map<ll, int> f;

int main() {
  scanf("%d%d %s", &n, &k, s + 1);
  ll qs = 0;
  int mx = 0;
  for (int i = 1; i <= n; ++i) {
    if (s[i] == 'R')
      qs -= k;
    else
      ++qs;
    if (f[qs] == 0 && qs != 0)
      f[qs] = i;
    else
      mx = max(mx, i - f[qs]);
  }

  printf("%d", mx);
  return 0;
}