# Balanced parentheses and brackets
### Problem
A string w of parentheses ( and ) and brackets [ and ] is balanced if it satisfies one of the following conditions:

w is the empty string

w = (x) for some balanced string x

w = [x] for some balanced string x

w = xy (concatenation) for some balanced strings x and y

For example, the string
w=([()][]())[()()]() is balanced, because w=xy, where x=([()][]()) and y=[()()]()

1. Describe and analyze an algorithm to determine whether a given string of parentheses and brackets is balanced.

2. Describe and analyze an algorithm to compute the length of a longest balanced subsequence of a given string of parentheses and brackets.

### Algorithm Description
1. This algorithm will use a stack to keep track of open and closed parenthesis/brackets. If character is an opening bracket/parenthsis '(' '[' then it will be pushed into stack, if it is a closing bracket/parenthsis however, then the stack will pop if not empty and compare the two elements, if they do not match it will return false.

fun balanced (word)
{
    var stack = [];
    
    if (len(word) < 2)    return false;
    
    for (var i = 1; i < len(word); i++)
    {
        if (word.subst(i-1,i) == "(" || word.subst(i-1,i) == "[")
        {
            stack.push(word.subst(i-1,i));
        }
        
        else if (word.subst(i-1,i) == ")" )
        {
            if (stack.pop != "(") || stack.isEmpty()) return false;
        }
        
        else if (word.subst(i-1,i) == "]")
        {
            if (stack.pop != "[") || stack.isEmpty()) return false;
        }
    }
    
    return stack.isEmpty();
}

2. The algorithm for this question will use dynamic programing to find the length. It will create a table dp[i][j](n x n array), where it stores the length of the longest balanced subsequence found within the substring starting at index i and ending at index j. There are two cases that can fill the table, the current open brace has its counterpart at the end of the string or it is somewhere in between.

fun longest_balanced_subsequence(word) {
    var n = len(word);
    // If the string is empty or has one character, return 0
    if (n < 2)    return 0;

    // Initialize an n x n array with all values as 0
    var dp = dp[n,0][n,0];

    // Iterate through all possible substring lengths, starting from 2
    for (var len = 2; i < n; i++){
        // For each length, iterate through all possible starting positions
        for (var start = 0; i < n - len; start++) {
            var end = start + len - 1;
            var match_value = 0;
            // Case 1: The characters at the ends form a matching pair
            if (word[start] == "(" AND word[end] == ")") OR (word[start] == "[" AND word[end] == "]") {
                    match_value = 2 + dp[i+1][j-1];
            }
            
            // Case 2: The subsequence is a concatenation of two smaller subsequences
            // Find the best possible split point 'k'
            var max_concat_val = 0;
            for (var k = start; k < end - 1; k++) {
                var current_concat = dp[start][k] + dp[k+1][end];
                if (current_concat > max_val)    max_concat_val = current_concat;
            }
            
            dp[i][j] = max(match_value, max_concat_value);
                        
        }
        return dp[0][n-1];
    }
}

### Correctness Proof
1. The algorithm correctly observes when a given string is a balanced string
**Base Case (string length is less than two):**
returns false as a string cannot be balanced if it is empty
**Case 1 (opening bracket/parenthesis):**
pushes element to stack for future referce
**Case 2 (incorrect closing bracket/parenthesis AND stack empty):**
if the string is balanced there should be an opposite element in the stack for the cycle to close (stack pop), if the incorrect one is popped or the stack is empty the algorithm returns false
**Case 3 (correct closing bracket/parenthesis AND stack is not empty):**
pops from stack and continues until there are no more elements in the given string

There are no other cases. QED.

2. **Base Case (string length is 1 or less):**
string cannot be balanced if its length is less than two therefore we return 0
**Case 1: The characters at the ends form a matching pair**
Adds two to the previous balanced count
**Case 2: The subsequence is a concatenation of two smaller subsequences**
There are no other cases. QED.

### Time Complexity
n = length of string
1. Goes through string only once
T(n) = O(n) + O(1)
T(n) = O(n)

2. Three nested loops
T(n) = O(n^3) + O(1)
T(n) = O(n^3)