Question 1: Convertible Balanced Bracket Sequence

Problem Statement:

Given a dataset of strings containing only parentheses, characters '(' and ')', the data represented by the string is valid if it is a balanced bracket sequence.One adjustment to the string can be made: at most one bracket can be moved from its original place to any other position in the string. The task is to determine whether, for each string, it is possible to balance the bracket sequence in 1 move or less. Return an array of the size of the dataset, where the i^th integer is 1 if the string can be converted into a balanced string, and 0 otherwise.

Note: A string s is a balanced bracket sequence if:

s is empty.
s is equal to "(t)", where t is a balanced bracket sequence.
s is equal to t_1,t_2, i.e., concatenation of t_1 and t_2 where t_1 and t_2 are balanced bracket sequences.

Example:

n = 3

dataset = [")(", "(()", "()"]

For the first string ")(", applying the operation to move the first bracket to the end results in "()", which is a balanced bracket sequence. (Result: 1)
For the second string "(()", it is impossible to convert it into a balanced bracket sequence. (Result: 0)
For the third string "()", it is already a balanced bracket sequence. (Result: 1)

Hence, the answer is [1, 0, 1].

ADD COMMENT • link 23 days ago admin 1.9k

Entering edit mode

Problem1 (Convertible Balanced Bracket Sequence) Solution

Overview

Think of a situation where you don't look at the whole string, but just the "broken" parts. If you simply pair up all the valid () brackets as you read them and pretend they don't exist, what are you left with?

You will always be left with some closing brackets followed by opening ones, like )...(. Because moving exactly one bracket can only fix at most one misplaced ) and one misplaced (, our leftover "broken" pile can have at most one of each to be fixable!

Approach

1. Cancel the Good Pairs

We can iterate through the string and keep track of unmatched opening brackets (. Whenever we see a closing bracket ), we check if we have a ( available to pair it with. If we do, we cancel them out! If we don't, we count it as an unmatched closing bracket.

2. Check the Leftovers

After looping through the entire string, we just look at what is left.

If we have 0 unmatched brackets, it was already balanced (0 moves).
If we have exactly 1 unmatched open and 1 unmatched close (like )(), we can fix it by moving one of them (1 move).
Any more than that (like ))((), and 1 move won't be enough to save it!

Implementation-:

function canBalanceInOneMove(dataset):
    create an empty array 'results'
    
    for each string 's' in dataset:
        unOpen = 0
        unClose = 0
        
        for i from 0 to length of s - 1:
            if s[i] == '(':
                unOpen = unOpen + 1
            else if s[i] == ')':
                // Match with an available open bracket if possible
                if unOpen > 0:
                    unOpen = unOpen - 1
                else:
                    unClose = unClose + 1
                    
        // Can only be fixed if there is at most 1 unmatched pair
        if unOpen <= 1 AND unClose <= 1:
            results.push_back(1)
        else:
            results.push_back(0)
            
    return results

Time Complexity

Time: O(N) - We only need to iterate through the string of brackets exactly once.
Space: O(1) - We don't even need a real Stack! We can just use two integer variables to keep count of the unmatched brackets.

ADD REPLY • link 23 days ago

admin 1.9k