4.2 Expression Evaluation / Parentheses

Demo: Longest Valid Parentheses — LC 32 (Hard — Google High)

Statement (Demo): শুধু '(' ও ')' দিয়ে গঠিত string s দেওয়া — সবচেয়ে দীর্ঘ valid parentheses substring-এর দৈর্ঘ্য বের করুন। উদাহরণ: s=")()())" → 4 | ⚡ len ≤ 3×10⁴

Approach: stack-এ index রাখুন, নিচে একটা base হিসেবে -1। ( এলে push; ) এলে pop — pop-এর পর stack খালি হলে এই ) টা নতুন base, নাহলে বর্তমান valid দৈর্ঘ্য = i - stack.top।

function longestValidParentheses(s) {
  const stack = [-1]; // base index
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") stack.push(i);
    else {
      stack.pop();
      if (stack.length === 0)
        stack.push(i); // নতুন base
      else best = Math.max(best, i - stack[stack.length - 1]);
    }
  }
  return best;
}

Complexity: Time O(n), Space O(n)