Please use Laptop/Desktop or any other large screen for the Mock Interview Session.

Valid parenthesis and range sum of BST



YouTube Video Thumbnail
Link

Watch above sample mock interview video to see how it works.
Login and Buy Premium to Start the Interview



Minimum Parentheses Removal for Valid String

Minimum Parentheses Removal for Valid String

Problem Statement

Given a string text consisting of lowercase letters and parentheses characters '(' and ')', your goal is to remove the fewest possible parentheses (either '(' or ')') from any positions so that the resulting string is correctly balanced.

A balanced parentheses string is defined as:

  • The empty string or a string containing only lowercase letters.
  • A concatenation of two balanced strings.
  • A string enclosed in a pair of matching parentheses, where the inside is balanced.

Examples

Input: text = "a(b(c)d)e)"
Output: "a(b(c)d)e"
Explanation: "a(b(cd)e)" or "ab(c)d)e" would also be valid outputs.

Input: text = "x)y(z"
Output: "xy(z"

Input: text = ")))((("
Output: ""
Explanation: Removing all parentheses results in a balanced empty string.

Input: text = "(h(e(l)l)o"
Output: "h(e(l)l)o"
    

Constraints

  • Length of text is between 1 and 120,000 characters.
  • text[i] is either a lowercase letter, '(', or ')'.