All Balanced Strings from Minimum Parenthesis Insertions
Updated
Problem statement
You are given a string s made of the characters '(', ')' and lowercase English letters. You may insert the characters '(' and ')' anywhere in s: before the first character, between two characters, or after the last one. You may not delete, change or move any character of s.
A string is balanced when, reading it from left to right, every ')' closes an earlier '(' that is still open, and no '(' is left open at the end. Letters do not affect balance, so a string without parentheses is balanced.
Let k be the minimum number of insertions that makes s balanced. Return every distinct balanced string that can be produced from s with exactly k insertions. Different insertion choices that produce the same text count as one string. Return the strings in ascending order, comparing character codes, so '(' comes before ')', which comes before every letter. If s is already balanced, k = 0 and the answer is [s].
Function
allMinimumInsertionStrings(s: String) → String[]Examples
Example 1
s = "a)b"return = ["(a)b","a()b"]- Scanning left to right, the
)has no earlier(to match, so at least one(must be inserted, and nothing else is missing. The minimum is one insertion. - The new
(must come before the): at the very start gives"(a)b", and right afteragives"a()b". - Putting it after the
)leaves that)unmatched. The two answers are listed in ascending order, and'('sorts before'a'.
Example 2
s = ")("return = ["()()"]- The
)needs a(inserted before it, and the(needs a)inserted after it, so the minimum is two insertions. - Both insertions have exactly one legal place, so the only answer is
"()()".
Example 3
s = "(("return = ["(())","()()"]- Both
(are unmatched, so two)must be inserted. - Putting both at the end gives
"(())". Putting one between the two(and one at the end gives"()()". - Putting both between the two
(gives"())(", which is not balanced. Different insertion choices that produce the same text count once, so the answer has two strings, sorted.
Constraints
1 <= s.length <= 20sconsists only of'(',')'and lowercase English letters.- The answer contains at most
200strings.
More Rubrik interview questions
- Insert into a Left-Complete Binary TreeONSITE INTERVIEW · Seen Oct 2026
- Thread-Safe Request Counts by AttributeONSITE INTERVIEW · Seen Oct 2026
- Delete and Freeze GameOA · Seen Nov 2026
- Delete K Subsets for Maximum ScoreOA · Seen Nov 2026
- Distribute Elements Into Two Arrays IIOA · Seen Nov 2026
- Minimum Replacements to Sort the ArrayOA · Seen Nov 2026
- Minimum Swaps To Binary PalindromeOA · Seen Apr 2026
- Get Minimum OperationsOA · Seen Nov 2024
- Horizontal Pod AutoscalerOA · Seen Nov 2024
- Stock PricesOA · Seen Nov 2024
Similar questions at other companies
- Inorder Tree String EquivalenceGoogle · ONSITE INTERVIEWGoogle interview questions
- Serialize and Deserialize a Binary TreeNVIDIA · PHONE SCREENNVIDIA interview questions
- Find File Paths in a Directory TreeUber · PHONE SCREENUber interview questions
- Word Search IIAmazon · ONSITE INTERVIEW
- Parse Boolean Rule ExpressionsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Remove Invalid ParenthesesMygate · ONSITE INTERVIEWMygate interview questions
- Nested JSON Schema ValidatorPinterest · ONSITE INTERVIEWPinterest interview questions
- N-Ary Tree Codec OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Spreadsheet Formula DependenciesAmazon Web Services · ONSITE INTERVIEWAmazon Web Services interview questions
- Longest Valid ParenthesesMathWorks · ONSITE INTERVIEWMathWorks interview questions