Balancing Act: Mastering the Valid Parenthesis Problem

#datastructures #algorithms #programming #typescript

Welcome back, algorithm enthusiasts! I hope you are enjoying this series revisiting the most frequently asked algorithms and data structures in technical interviews.

Throughout this series, we've covered a wide range of topics—from implementing custom Arrays and Hash Tables to solving common coding challenges like reversing strings, finding the maximum character in a string, and validating palindromes.

Today we are moving forward in difficulty and we are going to implement another one at the top of the notch. The balanced string also now as valid parenthesis problem.

Understanding the Problem

The problem statement for this challenge is as follows:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Now, let's consider the constraints we need to follow when solving this problem:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

This is interesting - we have specific constraints to follow. Let's analyze the problem statement: we have an input string containing only certain bracket characters, and we need to return a boolean indicating whether the input is valid according to the given rules.

"How do I solve this?" you might be asking yourself. The first time I faced this problem, I brute-forced it with numerous if statements and for loops. I even tried creating a map to count each character's appearances, then dividing and checking modular results to ensure each bracket pair balanced to zero.

I know, I know. Like Plato's cave allegory, I was blinded by my limited knowledge. After studying data structures and algorithms more thoroughly, I realized there's a simple and efficient way to solve this challenge using a common structure known as a stack.

Last In First Out

It's Friday night, and after a hard week, all you want is to play ranked matches in Street Fighter 6 for that dopamine rush from defeating novice players. But before that, you realize your dishes have gone unwashed for three days, and your wife is as furious as a Ken player who failed to trap you in the corner.

You need to tackle this stack of plates before you can even think about putting your hands on that controller. When you reach the last plate, you realize that you forgot to throw away the food remains, and now it's an indescribable, amorphous thing staring directly at you. This plate was the first in and the last out—and now you regret not maintaining this basic habit.

Stack of Plates

With the plates analogy, we've revealed the core concept of stacks: the first item to be stacked will be the last one to be retrieved. This principle is known as LIFO (Last In First Out) and explains how stacks work under the hood.

Now, imagine that instead of a pile of plates, there are brackets. This is the first step to solving this problem.

Before diving into the code, I need to clarify something first. To solve this exercise, we'll use a JavaScript array that functions as a stack. The array class has built-in methods that work perfectly for stack operations: push(), pop(), etc. We'll discuss stacks in more detail in the next post, but for now, I wanted to explain this so you won't be confused when you see an array named "stack."

Algorithm to Solve It

First, declare an empty array called stack where we'll store our characters.

const stack: string[] = [];

Next, let's create a map-like object to match opening and closing brackets. We'll use a simple object since we have a specific number of characters to map and need to reduce space complexity. Alternatively, we could use a Map object.

const pairs: Record<string, string> = {
  '(': ')',
  '{': '}',
  '[': ']',
};

Now that we've set up our variables, it's time to loop through our input string with a good old for...of loop.

for (let char of str) {}

In each iteration, we check for possible scenarios. If the character is a key in our pairs object, it means it's an opening bracket. For example: char = "(" → pairs["("] exists and its value is ")", so we push it onto the stack.

if (pairs[char]) {
  stack.push(char);
}

Otherwise, it must be a closing bracket. We need to verify it matches our last stacked opening bracket. We pop the last opening bracket from the stack and check if the current character is its corresponding closing bracket. If not, we return false because the string is not balanced.

else {
  const last = stack.pop();
  if (pairs[last!] !== char) {
    return false;
  }
}

Finally, if the stack is empty, it means the string is balanced; otherwise, it means some opening brackets don't have matching closing brackets. We simply return this evaluation.

return stack.length === 0;

With this, we've solved the problem. Simple, right? You just need the right knowledge to tackle it effectively. Pay close attention to how the stack interacts with opening brackets to fully grasp the core functionality of this solution.

Complete Typescript Implementation

function balancedString(str: string): boolean {
    const stack: string[] = [];
    const pairs: Record<string, string> = {
      '(': ')',
      '{': '}',
      '[': ']',
    };

    for (let char of str) {
        if (pairs[char]) {
      stack.push(char);
    } else {
          const last = stack.pop();
      if (pairs[last!] !== char) {
        return false;
      }
        }
    }

    return stack.length === 0;
}

Final Thoughts

Stacks and Queues are fundamental data structures that appear frequently in coding interviews. In upcoming posts, I'll explore these concepts in greater depth to equip you with the knowledge to tackle similar challenges. As this exercise demonstrates, understanding key Data Structures and Algorithms (DSA) principles enables you to craft elegant, efficient solutions rather than relying on brute force approaches.

As always, you can find this solution along with other algorithm implementations in my GitHub repository: https://github.com/RubenOAlvarado/algorithms
Until next time!