Longest Balanced Substring

In this approach, we will consider every substring and check if it can be the longest balanced substring. 

Below is the detailed approach: 

1. Initialize a variable ‘ANS’ = 0, this will store the length of the longest balanced substring.
2. Run a for loop from 0 to |'S'| - 1, where |'S'| is the length of string (say iterator = ‘i’):
   • Run a for loop from ‘i’ to |'S'| - 1, where |'S'| is the length of string (say iterator = ‘j’):
     • If substring(‘i’, ‘j’) is balanced, then:
       • ‘ANS’ = max (‘ANS’ , ‘j’ - ‘i’ + 1).
3. Finally, return ‘ANS’.

To check if a string is balanced or not, follow the below steps:

1. Make two variables ‘O’(count of open parentheses) and ‘C’ (count of close parentheses) and initialize them with zero.
2. Now iterate on the string, if the ith character is ‘(‘, increment ‘O’, else increment ‘C’.
3. If at any index ‘C’ becomes greater than ‘O’ or ‘O’ becomes greater than N, then the sequence is not balanced.
4. In the end, if ‘O’ is equal to ‘C’, then the string is balanced.

In this approach, for each index, we will find the length of the longest balanced substring starting at this index. Because, for any index i, if there is an index j such that substring(i, j) is not balanced, then for any index k greater than j, substring(i,k) is also not balanced.

Below is the detailed algorithm:

Note: N denotes the length of the given string.

1. Initialize a variable ‘MAXLENGTH’ = 0, this will store the length of the longest balanced substring.
2. Iterate on the indices from 0 to ‘N’-1. Let ‘i’ denote the current index.
   • Make a stack to store the indices of the open parenthesis.
   • Let ‘L’ denote the length of the longest balanced substring starting from index i.
   • Iterate on the indices from ‘i’ to ‘N-1’, let ‘j’ denote the current index.
     • If the ‘S[j]’ is equal to ‘(‘, push ‘j’ in the stack.
     • Else:
       • If the stack is empty, there will be no further indices such that substring(‘i’, ‘j’) is balanced.
       • Else, pop the top element from the stack and if the stack becomes empty, update the value of ‘L’.
       • If stack becomes empty then:
         • ‘MAXLENGTH’ = max(‘MAXLENGTH’ , ‘j’ - ‘i’ + 1).
3. Finally, return ‘MAXLENGTH’.

In this approach, for each index, we will find the length of the longest balanced substring ending at this index.

For example, if the given string is “()()”,

• For index 0, no balanced substring ending at this index.
• For index 1, there is only one balanced substring ending at this index {“()”}.
• For index 2, no balanced substring ending at this index.
• For index 3, there are two balanced substrings ending at this index {“()”, “()()”}, but “()()” is the longest.
• We will use a stack to find the length of the longest balanced substring ending at some index.

How will the stack work?

For example, if the given string is “())()”,

• For index 0, it contains an open parenthesis, so push this index in the stack.
• For index 1, the length of the longest balanced substring ending at this index is 2. So, after popping the top element, the new top element of the stack should be -1, because (1 - (-1)) = 2.
• For index 2, the length of the longest balanced substring ending at this index is 0. So, after popping the top element, the stack should be empty.
• For index 3, it contains an open parenthesis, so push this index in the stack.
• For index 4, the length of the longest balanced substring ending at this index is 2. So, after popping the top element, the new top element of the stack should be 2, because (4 - 2) = 2.

Below is the detailed algorithm:

Note: ‘N’ denotes the length of the given string.

1. Make a stack to store the indices.
2. Push -1 in the stack.
3. Iterate on the indices of the given string, let ‘i’ denote the current index.
   • If ‘S[i]’ is equal to ‘(‘, push the current index in the stack.
   • Else,
     • Pop the top element from the stack.
     • If the stack is empty, the length of the longest balanced substring ending at this index is 0, push the current index in the stack.
     • Else, let ‘j’ denote the top element of the stack, then the length of the longest balanced substring ending at this index is (i-j).
4. Return the length of the longest balanced substring.

In this approach, we will use dynamic programming to find the longest balanced substring.

Following is the detailed algorithm:

1. Make an array ‘DP’, where ‘DP[i]’ is equal to the length of the longest balanced substring ending at index ‘i’.
2. Initialize a variable ‘MAXLENGTH’ = 0, this will store the length of the longest balanced substring.
3. Run a loop from 0 to length of  ‘STR’ (say iterator = ‘i’):
   • If ‘S[i]’ = ‘(‘, then ‘DP[i]’ = 0.
   • If ‘S[i]’ = ‘)’, then we have to find an index ‘j’, such that substring(‘j’, ‘i’) is balanced.
   •  
   • If ‘S[i-1]’ = ‘(‘, then ‘j’ = ‘i-1’.
   • Else if, ‘S[i - DP[i-1]-1]’ = ‘(‘, then ‘j’ = ‘i’ - ‘DP[i-1]’ - 1.
     • If there is no possible j, then ‘DP[i]’ = 0.
     • Else, ‘DP[i]’ = (‘i’-’j’+1) + ‘DP[j-1]’.
        
   • ‘MAXLENGTH’ = max(‘DP[i]’ , ‘MAXLENGTH’).
4. Finally, return ‘MAXLENGTH’.

In this approach, we will use a similar algorithm that we used in Approach 1 to check whether a string is balanced or not.
 

Below is the detailed algorithm:

1. Make three variables  ‘maxLength’ (stores the length of longest balanced substring), ‘O’(count of open parentheses), and ‘C’ (count of close parentheses), and initialize them with zero.
2. Now iterate on the string indices from 0 to (N-1), if the ith character is ‘(‘, increment ‘O’, else increment ‘C’.
3. For an index, if ‘O’ is equal to ‘C’, then update the ‘maxLength’, maxLength = max(maxLength, 2*O).
4. If ‘C’ becomes greater than ‘O’, then reset ‘C’, ‘O’ to 0.
5. Now repeat the steps from 2 to 5 but with few changes.
6. Iterate on the string indices from (N-1) to 0, if the ith character is ‘(‘, increment ‘O’, else increment ‘C’.
7. For an index, if ‘O’ is equal to ‘C’, then update the ‘maxLength’, maxLength = max(maxLength, 2*O).
8. If ‘O’ becomes greater than ‘C’, then reset ‘C’, ‘O’ to 0.