Valid Parentheses Solution for Accenture

Company: Accenture · Difficulty: Easy · Topics: String, Stack

Problem Statement

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Key Understanding:

We have three types of brackets: (), {}, []
Each opening bracket must have a matching closing bracket
Brackets must be properly nested (LIFO order)
The string can contain any combination of these brackets

Examples

Example 1:

Input: s = "()"

Output: true

Explanation:

Simple valid parentheses
'(' is opened and ')' closes it properly
Visual representation: ( ) ✓

Example 2:

Input: s = "()[]{}"

Output: true

Explanation:

All brackets are properly closed
'(' is closed by ')', '[' is closed by ']', '{' is closed by '}'
Visual representation: ( ) [ ] { } ✓

Example 3:

Input: s = "(]"

Output: false

Explanation:

Opening parenthesis '(' is closed by wrong bracket ']'
'(' expects ')' but gets ']'
Visual representation: ( ] ✗

Example 4:

Input: s = "([)]"

Output: false

Explanation:

Brackets are not closed in correct order
'(' is opened, then '[' is opened, but ')' closes '(' before '[' is closed
Visual representation: ( [ ) ] ✗

Example 5:

Input: s = "{[]}"

Output: true

Explanation:

Properly nested brackets
'[' is opened and closed by ']', then '{' is closed by '}'
Visual representation: { [ ] } ✓

Intuition

The key insight is that we need to match each closing bracket with its corresponding opening bracket. The last opening bracket should be closed first (LIFO - Last In, First Out), which suggests using a stack.

Core Concept:

When we encounter an opening bracket, we push it onto a stack
When we encounter a closing bracket, we check if it matches the most recent opening bracket (top of stack)
If it matches, we pop the opening bracket from the stack
If it doesn't match or stack is empty, the string is invalid

Why Stack Works:

Stack follows LIFO (Last In, First Out) principle
This matches the requirement that the most recently opened bracket must be closed first
We can easily check if brackets are properly nested

Approach

Approach 1: Stack (Optimal)

Algorithm:

1. Initialize an empty stack

2. For each character in the string:

If it's an opening bracket ('(', '{', '['), push it onto the stack
If it's a closing bracket (')', '}', ']'):
Check if stack is empty (if yes, return false)
Pop the top element from stack
Check if the popped bracket matches the current closing bracket
If no match, return false

3. At the end, check if stack is empty (if not, return false)

4. Return true if all checks pass

Why This Works:

Stack ensures that the most recently opened bracket is checked first
Each closing bracket must match its corresponding opening bracket
Empty stack at the end ensures all brackets are properly closed

Complexity Analysis:

Time: O(n) - Single pass through the string
Space: O(n) - Worst case when all characters are opening brackets

Approach 2: Array as Stack

Algorithm:

1. Use an array to simulate stack operations

2. Keep track of stack size manually

3. Same logic as stack approach but with array implementation

Why This Works:

Functionally equivalent to stack approach
More explicit control over stack operations
Can be more efficient in some implementations

Complexity Analysis:

Time: O(n) - Single pass through the string
Space: O(n) - Worst case when all characters are opening brackets

Approach 3: Character Counting (Limited)

Algorithm:

1. Count opening and closing brackets separately

2. Check if counts are equal for each bracket type

3. Only works for simple cases, fails for nested brackets

Why This Doesn't Work:

Cannot handle nested brackets like "([)]"
Cannot ensure proper ordering
Only checks quantity, not structure

Complexity Analysis:

Time: O(n) - Single pass through the string
Space: O(1) - Only constant variables needed

Dry Run

Let's trace through Example 1: s = "()"

Stack Approach:

Initial State: stack = [], i = 0

Step 1: i = 0, char = '('

'(' is an opening bracket
Push '(' onto stack
stack = ['(']

Step 2: i = 1, char = ')'

')' is a closing bracket
Check if stack is empty: No
Pop top element: '('
Check if '(' matches ')': Yes
stack = []

Step 3: End of string

Check if stack is empty: Yes
Return true

Example 4: s = "([)]"

Initial State: stack = [], i = 0

Step 1: i = 0, char = '('

Push '(' onto stack
stack = ['(']

Step 2: i = 1, char = '['

Push '[' onto stack
stack = ['(', '[']

Step 3: i = 2, char = ')'

')' is a closing bracket
Pop top element: '['
Check if '[' matches ')': No
Return false

Key Insights

1. LIFO Principle: Stack naturally implements the required LIFO behavior

2. Matching Pairs: Each closing bracket must match its corresponding opening bracket

3. Nesting Order: Brackets must be properly nested (cannot close outer bracket before inner)

4. Stack Size: Maximum stack size is n/2 (when all characters are opening brackets)

5. Early Termination: Can return false as soon as a mismatch is found

Edge Cases

1. Empty String: Should return true (no brackets to validate)

2. Single Opening Bracket: Should return false (no closing bracket)

3. Single Closing Bracket: Should return false (no opening bracket)

4. Unmatched Opening Brackets: Should return false (stack not empty at end)

5. Unmatched Closing Brackets: Should return false (stack empty when closing bracket encountered)

6. Mixed Valid/Invalid: Should return false as soon as first mismatch is found

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Stack (Optimal)

Time Complexity: O(n) - We traverse the string once

Space Complexity: O(n) - We store at most n/2 opening brackets

Advantages:

Most intuitive and efficient approach
Handles all edge cases correctly
Easy to understand and implement
Natural fit for the problem

Disadvantages:

Uses extra space proportional to input size
Requires understanding of stack data structure

Solution 2: Array as Stack

Time Complexity: O(n) - We traverse the string once

Space Complexity: O(n) - We store at most n/2 opening brackets

Advantages:

More explicit control over stack operations
Can be more efficient in some implementations
Easier to debug and trace

Disadvantages:

More complex implementation
Same space complexity as stack approach

Solution 3: Character Counting (Limited)

Time Complexity: O(n) - We traverse the string once

Space Complexity: O(1) - We use only constant space

Advantages:

Constant space usage
Simple implementation

Disadvantages:

Incorrect for nested brackets
Cannot handle proper ordering
Not suitable for this problem