การกลับสตริงระหว่างวงเล็บ (Reverse Substrings Between Each Pair of Parentheses) ใน C++

ให้ String s ประกอบด้วยตัวอักษรพิมพ์เล็กและวงเล็บ () ต้อง **กลับลำดับตัวอักษรในแต่ละคู่วงเล็บ** เริ่มจาก **คู่ในสุด (Innermost)** และ **ผลลัพธ์ต้องไม่มีวงเล็บเหลือ**

ตัวอย่าง

Input: "(hel(lowo)rld)"

1. วงเล็บในสุด: (lowo) -> owol => String กลายเป็น "(helowolrld)"
2. วงเล็บนอก: (helowolrld) -> "dlrowoleh"

Output: "dlrowoleh" (ตัวอย่างในโจทย์มี typo ให้ "dlrlowoleh" แต่ Logic ถูกต้องคือ "dlrowoleh")

อัลกอริทึม: Stack + Jump Pointers (O(N))

1. Preprocess: หา **Matching Parentheses** ทุกคู่ -> เก็บใน Array par[i] = j (Index ของวงเล็บคู่)
2. เดินผ่าน String ด้วย Pointer i และ Direction d = +1/-1:
   • เจอวงเล็บ (( หรือ )) -> **กระโดด** ไปคู่ของมัน (i = par[i]) และ **กลับทิศทาง** (d = -d)
   • เจอตัวอักษร -> Append เข้า Result

วิธีนี้ "ข้าม" วงเล็บไปมาได้ใน O(1) ต่อคู่ ทำให้ Overall O(N)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    string reverseParentheses(string s) {
        int n = s.size();
        vector<int> par(n);        // par[i] = index ของวงเล็บคู่
        stack<int> st;             // Stack เก็บ index ของ '('

        // 1. Build matching pairs
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') {
                st.push(i);
            } else if (s[i] == ')') {
                int j = st.top(); st.pop();
                par[i] = j;
                par[j] = i;
            }
        }

        // 2. Traverse with direction flipping
        string ret = "";
        for (int i = 0, d = 1; i < n; i += d) {
            if (s[i] == '(' || s[i] == ')') {
                i = par[i];  // Jump to matching bracket
                d = -d;      // Reverse direction
            } else {
                ret += s[i]; // Append character
            }
        }
        return ret;
    }
};

Input / Output

Input:  "(hel(lowo)rld)"
Output: "dlrowoleh"

ความซับซ้อน (Complexity)

• Time: O(N) — ทุก Index ถูก Visit สูงสุด 2 ครั้ง (หนึ่งครั้งต่อ Direction)
• Space: O(N) — Array par และ Stack

จุดสำคัญ (Key Insight)

แทนที่จะ Reverse จริงๆ (ซึ่งใช้ O(N²) worst case) เรา **จำลองการเดิน** โดย **กระโดดข้ามวงเล็บ** และ **กลับทิศทาง** เทคนิคนี้ใช้ได้กับโจทย์ Bracket Reversal หลายรูปแบบครับ