Generate All Balanced Parenthesis Strings with n Pairs in Sorted Order
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
Input: n = 1
Output: ["()"]
```
**Example 2**
```text
Input: n = 2
Output: ["(())", "()()"]
```
**Example 3**
```text
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
```
Overview: 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.
Read the full Salesforce Software Engineer interview experience this question came from