Longest Valid Parentheses
Stacks
JavaScript
Problem:
Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.
Example:
Input String: ‘(‘
Output: 0
There is no closing parentheses.
Input String: ‘))’
Output: 0
There is no valid parentheses substring.
Input String: ‘))()’
Output: 2
The longest valid parentheses substring is “()”.
Input String: ‘)()())(()()())’
Output: 8
The longest valid parentheses substring is “(()()())”.
Algorithm:
To solve this, we use a stack to find the valid parentheses substring. When encountering an unmatched closing parenthesis, we check for the next valid substring. By keeping track of the length and the starting index of each valid substring, we can identify the longest valid substring.
Steps:
- Loop through the string and push all opening parentheses onto the stack until a closing parenthesis is encountered.
- For every opening parenthesis, increment the startIndex.
- When a closing parenthesis is encountered:
- If the stack is not empty, pop the opening parenthesis from the stack. This forms a matching parentheses pair. Decrement the startIndex and increase the length of the valid substring by 2.
- If the stack is empty, it means the valid substring ends at the current index. Continue searching for the next valid substring from the next index.
- Finally, find the maximum length among all valid substrings.
Solution & Visualize:
The animation/visualization below illustrates the algorithm. Feel free to experiment with different input values.
Result
Code
Input:
Output:
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
let string = args[0];
let length = 0;
let maxLength = 0;
let startIndex = 0;
let validParentheses = {};
const stack = new Stack(
[],
{
name: 'Stack',
description: 'This stack will hold the opening parentheses.'
}
);
for (var i = 0; i < string.length; i++) {
if (string[i] == '(') {
animatorModule.displayComment(
'Loop through the string and push all opening brackets onto the stack. <br>'
+ highlightCharacter(string, i),
500
);
stack.push('(');
startIndex++;
} else {
if (! stack.isEmpty()) {
animatorModule.displayComment(
'When a closing parentheses is encountered, pop the top element from the stack. <br>'
+ highlightCharacter(string, i),
500
);
stack.pop();
length +=2;
startIndex--;
animatorModule.displayComment(
'Current valid substring. <br>'
+ highlightSubstring(string, startIndex, length),
750
);
} else {
if (length > 0) {
animatorModule.displayComment(
'Unmatched closing parentheses. <br>'
+ highlightCharacter(string, i),
1500
);
animatorModule.displayComment(
'A valid substring is found, continue searching for the next substring. <br>'
+ highlightSubstring(string, startIndex, length),
1500
);
}
startIndex = i + 1;
length = 0;
}
}
validParentheses[startIndex] = length;
}
let key = Object.keys(validParentheses)
.reduce((a, b) => validParentheses[a] > validParentheses[b] ? a : b);
maxLength = validParentheses[key];
animatorModule.displayOutput(maxLength);
animatorModule.displayComment(
'Longest valid parentheses: <br>' + highlightSubstring(string, parseInt(key), maxLength)
);
return maxLength;
}
class Stack {
metaData = {
'name': 'Stack',
'description': '',
'animation_duration': 1500,
}
constructor(initialData, metaData) {
this.initialData = [...initialData];
this.metaData = Object.assign({}, this.metaData, metaData);
this.stackDisplayer = new StackDisplayer(initialData, this.metaData);
this.stackId = this.stackDisplayer.display();
}
getStackData() {
return this.initialData;
}
push(value) {
this.initialData.push(value);
// Perform the animation
animatorModule.performPushAnimation(this.stackId, value);
}
pop() {
if (this.initialData.length == 0) return;
const value = this.initialData.pop();
// Perform the animation
animatorModule.performPopAnimation(this.stackId, value);
return value;
}
top() {
if (this.initialData.length == 0) return;
const value = this.initialData[this.initialData.length - 1];
return value;
}
isEmpty() {
return this.initialData.length === 0;
}
}
class StackDisplayer {
constructor(initialData, metaData) {
this.initialData = initialData;
this.metaData = metaData;
}
display() {
// Display stack on the screen
const stackTemplate = document.getElementById('stack-template');
const clone = stackTemplate.content.cloneNode(true);
const stackCount = document.getElementsByClassName('stack-wrapper').length + 1;
// Add an unique ID to the clone
const stackWrapperId = 'stack-' + stackCount;
const stackWrapper = clone.querySelector('.stack-wrapper');
stackWrapper.id = stackWrapperId;
// Add initial stack items
const stackElement = clone.querySelector('.stack');
while(this.initialData.length) {
stackElement.insertAdjacentHTML(
'beforeend',
'<div class="stack-item">'+ this.initialData.pop() +'</div>'
)
}
clone.querySelector('.stack-description h4')
.textContent = this.metaData.name;
clone.querySelector('.stack-description p')
.textContent = this.metaData.description;
document.getElementById('stack-visualizer')
.appendChild(clone);
return stackWrapperId;
}
}
class AnimationList {
animations = [];
length() {
return this.animations.length;
}
push(animation) {
this.animations.push(animation);
}
shift() {
return this.animations.shift();
}
}
let animatorModule = (function() {
let animations = new AnimationList();
let animationsRunning = false;
let animationSpeed = 1200;
function getMoveDownAnimation(animation) {
let topElement = animation.stackElement.children[0];
let distance = animation.stackElement.offsetHeight;
if (topElement) {
distance = topElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().height
- 2; // Margin bottom
}
let moveDownAnimation = [
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
(0.2 * distance) + 'px',
(0.37 * distance) + 'px',
(0.55 * distance) + 'px',
(0.7 * distance) + 'px',
(0.87 * distance) + 'px',
distance + 'px',
distance + 'px'
];
return moveDownAnimation;
}
function getMoveUpAnimation(animation) {
let topElement = animation.stackElement.children[0];
let distance = topElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().y;
let moveUpAnimation = [
(distance - 0.95 * distance) + 'px',
(distance - 0.87 * distance) + 'px',
(distance - 0.7 * distance) + 'px',
(distance - 0.55 * distance) + 'px',
(distance - 0.37 * distance) + 'px',
(distance - 0.2 * distance) + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px'
];
return moveUpAnimation;
}
function pushAnimate(animation) {
animation.pushElement.textContent = animation.value;
let pushAnimationKeyFrames = {
// 25% - Show element
opacity: ['0', '0.3', '0.7', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'],
left: ['0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px'],
top: getMoveDownAnimation(animation),
offset: [0, 0.08, 0.16, 0.25, 0.25, 0.31, 0.37, 0.43, 0.5, 0.56, 0.62, 0.68, 0.73, 0.78, 0.83, 0.88, 0.93, 0.98, 1]
};
let duplicateElement = animation.pushElement.cloneNode(true);
duplicateElement.classList.remove('hidden');
// TODO: Increase the height of the stack before pushing
let pushAnimation = animation.pushElement.animate(pushAnimationKeyFrames, animationSpeed);
return new Promise((resolve) => {
return pushAnimation.finished.then(() => {
animation.stackElement.prepend(duplicateElement);
resolve(`Push Animation completed!`);
});
})
}
function popAnimate(animation) {
let popAnimationKeyFrames = {
bottom: getMoveUpAnimation(animation),
left: ['0', '0', '0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px'],
offset: [0, 0.07, 0.15, 0.22, 0.3, 0.37, 0.45, 0.52, 0.6, 0.67, 0.75, 0.82, 0.9, 1]
};
let topElement = animation.stackElement.children[0];
let popAnimation = topElement.animate(popAnimationKeyFrames, animationSpeed);
// The animation is not smooth
// So remove the item before animation is completed
setTimeout(() => {
topElement.remove();
animation.popElement.textContent = topElement.textContent;
}, animationSpeed - 200);
return new Promise((resolve) => {
return popAnimation.finished.then(() => {
// topElement.remove();
// animation.popElement.textContent = topElement.textContent;
resolve(`Pop Animation completed!`);
});
})
}
function displayCommentAnimate(animation) {
return new Promise((resolve) => {
document.getElementsByClassName('sv-comment')[0]
.innerHTML = animation.value;
setTimeout(() => {
resolve('Comment displayed!');
}, animation.timeout);
})
}
function displayOutputAnimate(animation) {
return new Promise((resolve) => {
let outputELement = document.getElementById('final-output');
outputELement.innerHTML = animation.value;
resolve('Output displayed!');
})
}
function runSingleAnimation(animation) {
switch (animation.type) {
case 'push':
return pushAnimate(animation);
break;
case 'pop':
return popAnimate(animation);
break;
case 'display-comment':
return displayCommentAnimate(animation);
break;
case 'display-output':
return displayOutputAnimate(animation);
break;
}
}
function runAnimations() {
if (animationsRunning) return;
animationsRunning = true;
// Perform the animations one after the other
let animation = animations.shift();
runSingleAnimation(animation)
.then(() => {
animationsRunning = false;
if (animations.length()) {
runAnimations();
}
});
}
function getStackElements(stackId) {
let stackWrapper = document.getElementById(stackId);
return {
stackElement: stackWrapper.getElementsByClassName('stack')[0],
pushElement: stackWrapper.getElementsByClassName('push-element')[0],
popElement: stackWrapper.getElementsByClassName('pop-element')[0]
}
}
let performPushAnimation = function (stackId, value) {
let animationObject = Object.assign(
{type: 'push', value: value},
getStackElements(stackId)
);
animations.push(animationObject);
runAnimations();
}
let performPopAnimation = function (stackId, value) {
let animationObject = Object.assign(
{type: 'pop', value: value},
getStackElements(stackId)
);
animations.push(animationObject);
runAnimations();
}
/**
* Set the animation duration.
*
* @param flot speed Duration in seconds (1, 2.5...)
*/
let setAnimationSpeed = function (speed) {
animationSpeed = speed * 1000;
}
let displayComment = function (comment, timeout = 0) {
let animationObject = {
type: 'display-comment',
value: comment,
timeout: timeout
};
animations.push(animationObject);
runAnimations();
}
let displayOutput = function (output) {
let animationObject = {
type: 'display-output',
value: output
};
animations.push(animationObject);
runAnimations();
}
let clearAnimations = function () {
animations = new AnimationList();
animationsRunning = false;
}
return {
performPushAnimation: performPushAnimation,
performPopAnimation: performPopAnimation,
setAnimationSpeed: setAnimationSpeed,
displayComment: displayComment,
displayOutput: displayOutput,
clearAnimations: clearAnimations
}
})();