Skip to main content

Minimum moves for balancing brackets

You’re given a non-empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition of being stable is as follows:
  1. An empty string is stable.
  2. If S is stable, then {S} is also stable.
  3. If S and T are both stable, then ST (the concatenation of the two) is also stable.
All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{.
The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa.

 Solution Heuristics: Traverse the string. When the number of opening braces( { ) matches the number of closing braces ( } ), the string is balanced. Else it's not balanced. So count both of them. Make a list. Insert only opening braces. If a closing brace is found delete one brace( if the size of the list is > 0 ) from the list. Because they would make a pair. If the list is empty then we'll convert the just found closing brace to opening brace and insert into the list. This will count as a move. When the iteration is finished, we will reverse half of the braces in the list and they will also count as moves. Now, find out the total summation of the moves for result.
Practice Problem: SPOJ ANARC09A - Seinfeld
Labels:

Comments

Post a Comment

Popular posts from this blog

SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 } Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } A node contains-  [ START & END is a node's segment limit ] Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous) Suffix is the maximum sum ending at END, start can be anywhere. There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix   (which will make the suffix contiguous). Sum : leftChild's sum + rightChild's sum. MAX Maximum of  -  prefix (result is in the node, starts from START but doesn't end in END ) suffix  (result is in the node, doesn't start from START but surely ends in END ) leftChild's max ( result is in left ...
14 comments
Read more

SPOJ 95 - STPAR - Street Parade

Problem Statement Heuristics:   Let, N be the number which is next in fixed order. Take an input X , if it is equal to N then next number will be n++. If not, then search for N in the side lane and after finishing the search, put X in the side lane. After all X is processed but N is not found in either X or side lane, then the order is not possible. Solution:
Post a Comment
Read more

SPOJ-PIGBANK | Unbounded Knapsack ( Minimization)

Unbounded Knapsack : Given a knapsack weight W and a set of N items with certain value Vi and weight W i , we need to calculate minimum amount that could make up this quantity exactly. To have a more clear understanding of this problem, see SPOJ-PIGBANK Sample Problem : We're given a box which can hold maximum W weight. There are N various coins each of value Vi and Weight Wi. We need to fill the box with total W weight with any number of coins of any value. Note that coins are unlimited.  100 ----- W 2 ------- N 1 1 ----- vi,wi 30 50 --- vi,wi Answer of the problem above is, 60. If we take 2 coins of value 30, weight 50, we'll get exactly weight 100 with a minimum value of 60. Algorithm : This is a DP solution. To get the solution for W=100, we'll solve subproblems first. Let dp[W+1]  be an array which will store the subproblems solutions. In the end, dp[W] will give us the minimum amount. Subproblems soultion will be the minimum of taking the coin Vk ...
Post a Comment
Read more