Longest Valid Parentheses

                                            
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        if (n == 0) return 0;
        
        stack<int> st;
        st.push(-1);
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                } else {
                    maxLen = max(maxLen, i - st.top());
                }
            }
        }
        
        return maxLen;
    }
};

                                            
class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        
        return max;
    }
}

                                            
class Solution(object):
    def longestValidParentheses(self, s):
        stack = [-1]
        max_length = 0
        
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_length = max(max_length, i - stack[-1])
        
        return max_length

                                            
int longestValidParentheses(char* s) {
    int max = 0;
    int n = strlen(s);
    int* dp = (int*)malloc(sizeof(int) * n);
    memset(dp, 0, sizeof(int) * n);
    
    for(int i = 1; i < n; i++) {
        if(s[i] == ')') {
            if(s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            max = fmax(max, dp[i]);
        }
    }
    
    free(dp);
    return max;
}

                                            
public class Solution {
    public int LongestValidParentheses(string s) {
        if (string.IsNullOrEmpty(s)) {
            return 0;
        }
        
        int max = 0;
        Stack<int> stack = new Stack<int>();
        stack.Push(-1);
        
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push(i);
            } else {
                stack.Pop();
                if (stack.Count == 0) {
                    stack.Push(i);
                } else {
                    max = Math.Max(max, i - stack.Peek());
                }
            }
        }
        
        return max;
    }
}

                                            
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let stack = [-1];
    let max = 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);
            } else {
                max = Math.max(max, i - stack[stack.length - 1]);
            }
        }
    }
    
    return max;
};

                                            
function longestValidParentheses(s: string): number {
    const stack: number[] = [-1];
    let maxLen = 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);
            } else {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }

    return maxLen;
};

                                            
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function longestValidParentheses($s) {
        $stack = [];
        $stack[] = -1;
        $max_length = 0;
        
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i] == '(') {
                $stack[] = $i;
            } else {
                array_pop($stack);
                if (empty($stack)) {
                    $stack[] = $i;
                } else {
                    $max_length = max($max_length, $i - end($stack));
                }
            }
        }
        
        return $max_length;
    }
}

                                            
class Solution {
    func longestValidParentheses(_ s: String) -> Int {
        var stack = [-1]
        var longest = 0
        
        for (index, char) in s.enumerated() {
            if char == "(" {
                stack.append(index)
            } else {
                stack.removeLast()
                if stack.isEmpty {
                    stack.append(index)
                } else {
                    longest = max(longest, index - stack.last!)
                }
            }
        }
        
        return longest
    }
}

                                            
class Solution {
    fun longestValidParentheses(s: String): Int {
        var maxLen = 0
        val stack = mutableListOf<Int>()
        stack.add(-1)
        for (i in s.indices) {
            if (s[i] == '(') {
                stack.add(i)
            } else {
                stack.removeAt(stack.size - 1)
                if (stack.isEmpty()) {
                    stack.add(i)
                } else {
                    maxLen = maxOf(maxLen, i - stack[stack.size - 1])
                }
            }
        }
        return maxLen
    }
}

                                            
class Solution {
  int longestValidParentheses(String s) {
    if (s.isEmpty) return 0;
    
    List<int> dp = List.filled(s.length, 0);
    int maxLen = 0;
    
    for (int i = 1; i < s.length; i++) {
      if (s[i] == ')') {
        if (s[i - 1] == '(') {
          dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
        } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
          dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
        }
        maxLen = maxLen > dp[i] ? maxLen : dp[i];
      }
    }
    
    return maxLen;
  }
}

                                            
func longestValidParentheses(s string) int {
    if len(s) == 0 {
        return 0
    }
    
    stack := []int{-1}
    maxLen := 0
    
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, i)
        } else {
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                stack = append(stack, i)
            } else {
                maxLen = max(maxLen, i - stack[len(stack)-1])
            }
        }
    }
    
    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {String} s
# @return {Integer}
def longest_valid_parentheses(s)
    stack = []
    max_length = 0
    stack.push(-1)
    
    for i in 0..s.length-1
        if s[i] == '('
            stack.push(i)
        else
            stack.pop
            if stack.empty?
                stack.push(i)
            else
                max_length = [max_length, i - stack.last].max
            end
        end
    end
    
    return max_length
end

                                            
object Solution {
    def longestValidParentheses(s: String): Int = {
        var maxLen = 0
        var stack = List(-1)
        
        for (i <- 0 until s.length) {
            if (s(i) == '(') {
                stack = i :: stack
            } else {
                stack = stack.tail
                if (stack.isEmpty) {
                    stack = i :: stack
                } else {
                    maxLen = Math.max(maxLen, i - stack.head)
                }
            }
        }
        
        maxLen
    }
}

                                            
impl Solution {
    pub fn longest_valid_parentheses(s: String) -> i32 {
        let mut stack: Vec<i32> = vec![-1];
        let mut max_length = 0;

        for (i, c) in s.chars().enumerate() {
            if c == '(' {
                stack.push(i as i32);
            } else {
                stack.pop();
                if stack.is_empty() {
                    stack.push(i as i32);
                } else {
                    max_length = max_length.max(i as i32 - stack.last().unwrap());
                }
            }
        }

        max_length as i32
    }
}

To solve this coding challenge, we need to understand how to identify the longest well-formed (valid) parentheses substring within a given string containing only the characters '(' and ')'. In this challenge, the primary idea is to keep track of the positions of parentheses using a stack, allowing us to efficiently determine the lengths of valid substrings.

Explanation

Problem Analysis:

A valid parenthesis substring is one where every opening parenthesis '(' has a corresponding closing parenthesis ')'.
Given input strings could vary in length from 0 to 30,000, and each character in the string is either '(' or ')'.
We need to return the longest valid parenthesis substring's length.

Approach:

Stack Utilization : Use a stack data structure to track indices of characters, which helps in pairing the parentheses.
Base Condition :

Start with a stack containing -1. This helps in edge cases where the substring starts from index 0.

Iteration :

Traverse each character in the string.
If the character is '(', push its index onto the stack.
If the character is ')', pop the top of the stack.

If the stack becomes empty after popping, push the current index onto the stack (this helps in maintaining the base for the next valid substring).
If the stack is not empty, calculate the length of the valid substring using the current index and the element at the new top of the stack.

Result Update :

During each iteration inside the loop, keep updating the maximum length of valid parentheses seen so far.

Detailed Steps in Pseudocode:

Initialize stack with -1,
max_length

with 0.
Traverse characters in the string using their index.
If character is '(', push its index to the stack.
If character is ')', pop from the stack:

If stack is empty, push the current index to the stack.
If the stack is not empty, calculate the length of valid substring using the current index and value at new stack top, and update
max_length

if greater.

Return the
max_length

after processing the entire string.

Pseudocode:

                                            
// Initialize the stack with -1 to handle base condition
stack = [-1]

// Initialize max_length to 0
max_length = 0

// Iterate through each character in the string
for each character in string with index i:
    // If the character is an opening parenthesis
    if character == '(':
        // Push the index of '(' onto the stack
        stack.push(i)
    else:
        // Pop the top of stack
        stack.pop()
        
        // If the stack is empty after popping
        if stack is empty:
            // Push the current index onto the stack as a base
            stack.push(i)
        else:
            // Calculate the length of the current valid substring
            length_of_valid_substring = index i - value at top of stack
            // Update max_length if the calculated length is greater
            if length_of_valid_substring > max_length:
                max_length = length_of_valid_substring

// Finally, return the maximum length of valid parentheses found
return max_length

This pseudocode ensures a concise yet comprehensive approach to solve the problem. It efficiently tracks pairs of parentheses and calculates the length of the longest valid substring by leveraging the stack's last-in, first-out (LIFO) nature.