w3resource

JavaScript: Longest Valid Parentheses

JavaScript String: Exercise-62 with Solution

Longest Valid Parentheses

Write a JavaScript function to get the length of the longest valid parentheses (well-formed) from a given string containing just the characters '[' and ']'.
Test Data:
The longest valid parentheses substring is "[]".
("[[]") -> 2
The longest valid parentheses substring is "[][]".
("][][]]") -> 4
No valid parentheses substring.
("") -> 0

Sample Solution:

JavaScript Code:

// Define a function called 'longest_Valid_Parentheses' with a parameter 'text'
const longest_Valid_Parentheses = (text) => {
  // Check if the input 'text' is not a string, return a message
  if (typeof text !== 'string') {
    return 'It must be string'
  }
  // Get the length of the input string 'text'
  const n = text.length 
  // Create an empty stack to store indices of brackets
  const stack = []
  // Initialize an array 'result' filled with -Infinity to store results
  const result = new Array(n).fill(-Infinity)
  // Loop through each character of the string 'text'
  for (let i = 0; i < n; i++) {
    // Get the current bracket
    const bracket = text[i]
    // If the current bracket is ']' and the top of the stack contains '[', mark the current index as valid
    if (bracket === ']' && text[stack[stack.length - 1]] === '[') {
      result[i] = 1
      result[stack[stack.length - 1]] = 1
      stack.pop()
    } 
    // If the current bracket is not a closing bracket, push its index to the stack
    else {
      stack.push(i)
    }
  }
  // Sum up all adjacent valid brackets
  for (let i = 1; i < n; i++) {
    result[i] = Math.max(result[i], result[i] + result[i - 1])
  }
  // Add 0 to the result array if there are no valid parentheses, so it will return 0 instead of -Infinity
  result.push(0)
  // Return the maximum value from the 'result' array
  return Math.max(...result)
}

// Test the 'longest_Valid_Parentheses' function with different input strings and output the result
console.log(longest_Valid_Parentheses("[[]")) // Output: 2
console.log(longest_Valid_Parentheses("][][]]")) // Output: 2
console.log(longest_Valid_Parentheses("")) // Output: 0

Output:

2
4
0

Explanation:

In the exercise above,

  • The function checks if the input "text()" is not a string, in which case it returns a message.
  • It initializes variables 'n' to store the length of the input string and 'stack' to store indices of brackets.
  • It initializes an array 'result' filled with '-Infinity' to store the results of valid parentheses lengths.
  • It iterates through each character of the input string 'text'.
  • If the current character is a closing bracket ']' and the top of the stack contains the corresponding opening bracket '[', it marks both indices as valid and pops the stack.
  • If the current character is not a closing bracket, it pushes its index to the stack.
  • It then iterates through the 'result' array to sum up all adjacent valid parentheses lengths.
  • It adds 0 to the 'result' array if there are no valid parentheses, so it will return 0 instead of '-Infinity'.
  • Finally, it returns the maximum value from the 'result' array, which represents the length of the longest valid parentheses substring.

Flowchart:

Flowchart: JavaScript: Longest Valid Parentheses

Live Demo:

See the Pen javascript-string-exercise-62 by w3resource (@w3resource) on CodePen.


For more Practice: Solve these Related Problems:

  • Write a JavaScript function that calculates the length of the longest valid parentheses substring using a stack-based approach.
  • Write a JavaScript function that uses dynamic programming to solve the longest valid parentheses problem.
  • Write a JavaScript function that handles edge cases such as strings with no valid parentheses.
  • Write a JavaScript function that validates the input and returns 0 if the string is empty or not valid.

Go to:


PREV : Longest Common Subsequence.
NEXT : Longest Palindromic Subsequence.

Improve this sample solution and post your code through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.