Katkat
Back

Generate All Balanced Parenthesis Strings with n Pairs in Sorted Order

SalesforceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Return every balanced string made of n opening and n closing parentheses, for n up to 8, sorted in ascending lexicographic order. It tests systematic generation of combinatorial strings under a validity constraint, with an exact canonical ordering of the output.

Given a number of pairs n, list every string made of exactly n opening brackets ( and n closing brackets ) that is balanced. A string is balanced when, reading from left to right, the number of ) characters seen so far never exceeds the number of ( characters seen so far, and the two counts are equal at the end.

Function Signature

def balanced_strings(n: int) -> List[str]:

Rules

  • Every string has length 2 * n and uses only the characters ( and ).
  • Include every balanced string exactly once.
  • Return the strings sorted in ascending lexicographic order by character code, where ( (code 40) sorts before ) (code 41). This is the order Python's sorted() produces for these strings.

Constraints

  • 1 <= n <= 8
  • For n = 8 the result contains 1,430 strings.

Examples

Example 1

Input: n = 1
Output: ["()"]

Example 2

Input: n = 2
Output: ["(())", "()()"]

Example 3

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]