Valid Parentheses
Easy About 10 min Free, no account needed
Are the brackets balanced and properly nested?
The brief
Given a string s of only ()[]{}, return true when the brackets are
balanced and properly nested.
The obvious approach repeatedly deletes innermost pairs ((), [], {}) until nothing
changes; every pass copies the whole string, so deep nesting costs O(n2).
The hidden test nests 20,000 brackets, so it's too slow. You need a single
O(n) pass.
Starter code
using System;
public class Solution
{
// TODO: return true when the bracket string is balanced and properly nested.
public bool IsValid(string s)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Stacks
- Use last-in, first-out state for nesting, matching and expression evaluation.
Related katas
- Maximum Bracket Depth Easy Free How deep do the parentheses nest? A counter beats a stack.
- Roll Back the Payload Ledger Easy Free Track staged payload totals while nested checkpoints are opened and rolled back.
- Remove All Adjacent Duplicates Easy Free Keep deleting adjacent equal pairs until none remain.
- Decode String Medium Free Expand k[encoded] patterns, nesting included.