Longest Valid Parentheses [Medium-Hard]

https://leetcode.com/problems/longest-valid-parentheses/

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

def longestValidParentheses(s: String): Int = {

  s.zipWithIndex
    .foldLeft(0 -> List.empty[(Char, Int)]) {
      case ((max, stack), (c, i)) =>
        stack match {
          case (c1, i1) :: rest if (c1 == '(' && c == ')') =>
            Math.max(
              i - rest.headOption.getOrElse('c' -> -1)._2,
              max
            ) -> rest
          case _ => max -> ((c, i) :: stack)
        }
    }
    ._1

}