FastPrepAll Balanced Strings from Minimum Parenthesis Insertions
Problems/All Balanced Strings from Minimum Parenthesis Insertions

All Balanced Strings from Minimum Parenthesis Insertions

Rubrik logoRubrik● HardFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Rubrik virtual onsite interview. The task is to list all the balanced strings you can reach by adding new parentheses to a given string. It is a relative of the well-known puzzle that counts the fewest additions needed. The candidate got as far as that count but did not reach the part that builds the repaired strings.

The report does not say whether only the fewest insertions count. It does not say how repeated results or the output order are handled, and it gives no limits or examples. Here, only strings built with the minimum number of insertions are returned. Each distinct string is listed once. The list is sorted by character code, so an opening parenthesis comes before a closing one, and both come before letters. Letters never affect balance. An input that is already balanced is returned as the only answer. The limits (at most 20 characters and at most 200 answers) and the examples are ours.

Our version is about 80% the same as the reported question.

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 after a gives "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 <= 20
  • s consists only of '(', ')' and lowercase English letters.
  • The answer contains at most 200 strings.

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
All Rubrik interview questionsSee Rubrik hiring insights
Saved
class Solution {
    public String[] allMinimumInsertionStrings(String s) {
        // Write your code here.
    }
}
Checking account…