Frontend School

Generate Valid Parenthesis Strings from Template

DSA
medium

Generate Valid Parenthesis Strings from Template

Medium
Backtracking
String
Recursion

Overview

In parsing and compiler design, correctly balanced parentheses are crucial for defining scope and structure. This problem explores the systematic generation of all possible valid parenthesis strings given a template that may contain wildcard characters. This is a fundamental problem that tests a candidate's ability to systematically explore possibilities and manage state, which is critical in many areas from language parsing to configuration validation.

What you need to do / Task

You are given a string template consisting of three types of characters:

  1. '(': An opening parenthesis.
  2. ')': A closing parenthesis.
  3. '?': A wildcard character that can be replaced by either an opening parenthesis '(' or a closing parenthesis ')'.

Your task is to generate all unique strings that can be formed by replacing each '?' in the template with either '(' or ')', such that the resulting string is a valid parenthesis string.

A string is considered a valid parenthesis string if:

  • Every opening parenthesis has a corresponding closing parenthesis.
  • Every closing parenthesis has a corresponding opening parenthesis.
  • Parentheses are properly nested (e.g., (()()) is valid, )( is not, (( is not).
  • The total number of opening parentheses equals the total number of closing parentheses.

You should return a list of all such unique valid parenthesis strings. The order of strings in the output list does not matter.

Input & output

Function Signature: function generateValidParenthesisStrings(template: string): string[]

  • template: A string containing '(', ')', and '?'.

Return Value:

  • A string[] (array of strings) containing all unique valid parenthesis strings that can be formed from the template.

Clarifications

  • An empty string "" is considered a valid parenthesis string. If the template is empty, the result should be [""].
  • The length of the template will always be the length of the resulting valid strings. Thus, if template.length is odd, no valid parenthesis string can be formed.
  • The resulting strings must be unique. Your algorithm should not produce duplicates (though with the problem's current constraints, unique paths in the recursion tree should yield unique strings).

Examples

1

Example 1

Input:

template = "(?)"

Output:

[]

Note:

The template has a length of 3. A valid parenthesis string must always have an even length. Since 3 is odd, no valid parenthesis string can be formed from this template.

2

Example 2

Input:

template = "()"

Output:

["()"]

Note:

The template contains no wildcards. The string "()" is already a valid parenthesis string.

3

Example 3

Input:

template = "????"

Output:

["(())","()()"]

Note:

For the template "????", two valid parenthesis strings can be formed: "(())" (replacing '?'s with '(( ))' respectively) and "()()" (replacing '?'s with '()()'). The order of the output strings does not matter.

Constraints

Constraints & assumptions

  • 1 <= template.length <= 15
  • The template string will only contain characters '(', ')', and '?'.
  • The order of strings in the output array does not matter.

What interviewers evaluate

  • Correctness: Does the solution correctly identify all valid parenthesis strings and only valid ones?
  • Algorithm Design: Is the backtracking approach logically sound, efficiently exploring the search space and pruning invalid paths early?
  • Edge Cases: Does the solution correctly handle templates that cannot form any valid strings (e.g., odd length, impossible combinations)?
  • Code Quality: Is the code clean, readable, well-structured, and appropriately uses helper functions or data structures (e.g., for string building)?
  • Time & Space Complexity: Can the candidate analyze and discuss the time and space complexity of their solution, especially considering the impact of pruning?

Loading editor...