# 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 1:
This algorithm solves question 1 by maintaining a stack that contains all the currently open brackets. Each time the algorithm encounters an open bracket, it pushes it to the top of stack, and every time it encounters a closed bracket, it checks to see if the type of the last opened bracket matches. If the algorithm ever encounters a closed bracket with no open brackets, or if the last opened bracket does not match this closed bracket, it returns false.

// input: string w consisting of parentheses and brackets
// output: boolean value indicating whether the string is balanced or unbalanced 

fun isBalanced(w) {
    // stack to hold opening brackets
    var stack = [];
    
    for (int i = 0; i < w.length(); i++) {
        var char = w[i];
        if (char == '(' or char == '[') {
            stack.push(char);
        }
        else if (char == ')' or char == ']') {
            // if there is a closed bracket with no open bracket to match
            if (stack.empty()) {
                // return false (unbalanced)
                return false;
            }
            var top = stack.top();
            stack.pop();
            
            // check if the types match
            if ((char == ')' and top != '(') or (char == ']' and top != '[')) {
                return false;
            }
        }
    }
    // if there are any open brackets, return unbalanced
    return stack.empty();
}

// sample call
// var w = "([()][]())[()()]()";
// isBalanced(w); // expect true

## correctness 1:
#### Theorem:
The algorithm correctly identifies whether or not a string w containing only the characters '(', '[', ')', and ']' is balanced (as defined by the problem) or unbalanced.
#### Proof:
We will prove the algorithms correctness through a loop invariant.

Invariant: At any point during the scan of w,
the stack consists of all unmatched opening brackets seen thus far, maintaining the order that they must be matched. The top of the stack contains the most recent opening bracket that must be matched next.

Before the loop starts and the stack is empty, the invariant trivially holds. Suppose the invariant contains the processing character char. There are two cases:
- Case 1: char is an opening bracket '(' or '['. The algorithm pushes char onto the stack, adding one new unmatched opening to the top. Invariant holds.
- Case 2: char is a closing bracket ')' or ']'. The algorithm correctly checks if the stack is empty, meaning there is no opening to match, and appropriately returns false. Otherwise, the algorithm pops the top symbol and checks whether top matches char (e.g., top = '[' and char = ']'). If they form a matching pair, the opening bracket is removed from the stack. Invariant holds. If they do not match, the algorithm returns false, as the string is unbalanced.

At the end of the scan, if the stack has no unmatched openings, it returns true. If the stack contains unmatched openings, it returns false. QED.

## complexity 1:
Since stack pops and pushes are O(1), and each character is only processed once, the time complexity of this algorithm is O(n).

## algorithm 2:
(algorithm description)

// my pseudocode jumps from rhythmic to c++ constantly im sorry
// input: string w consisting of parentheses and brackets
// output: length of the longest balanced subsequence of w

int longestBalancedSubseq(string w) {
    int n = w.length();
    // dpTable holds the lengths of the longest balanced subsequence within w[i...j]
    vector<vector<int>> dpTable(n, vector<int>(n, 0));
    
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i + length - 1 < n; i++) {
            int j = i + length - 1;
            // first case: substring surronded by matching pair
            if ((w[i] == '(' and w[j] == ')') or (w[i] == '[' and w[j] == ']')) {
                dpTable[i][j] = dpTable[i + 1][j - 1] + 2;
        }
            // second case: split substring
            for (int k = i; k < j; k++) {
                dpTable[i][j] = max(dpTable[i][j], dpTable[i][k] + dpTable[k+1][j]);
            }
        }
    }
    
    return dp[0][n - 1];
}

// sample call
// string w = "([()][]())[()()]()";
// longestBalancedSubseq(w) // expect 18 since the whole string is balanced

## correctness 2:
#### Theorem:
For any string w of length w, the algorithm correctly fills the dynamic programming table and returns the maximum possible length of balanced subsequences of w.
#### Proof:
We prove by induction dpTable[i][j] stores the longest balanced subsequence of w[i...j]'s length.

Base case:
For L = 0 or L = 1, (either an empty substring or a substring of length 1), it cannot contain a balanced pair, so dpTable[i][j] is trivially 0.

Inductive step: Assume dpTable[a][b] is correct for all substrings shorter than L. We will display correctness for substring w[i...j] of length L. A balanced subsequence within w[i...j] is formed in one of two ways.
1. w[i] is paired with w[j]. If the two indices form a valid pair ("()" or "[]"), then the inside portion w[i + 1... j - 1] must be balanced as well. The algorithm accounts for this situation with the line "dpTable[i][j] = dpTable[i + 1][j - 1] + 2;".
2. The subsequence is split in someplace. It is possible for the balanced subsequence to be the concatenation of smaller balanced parts split at index k, one within w[i...k] and another within w[k + 1...j]. The algorithm examines all possible splits and saves the maxmimum into the dpTable through the line "dpTable[i][j] = max(dpTable[i][j], dpTable[i][k] + dpTable[k+1][j]);".

These two cases account for all possible ways the a balanced subsequence can form out of string w, so the recurrence will always find the optimal length. By the inductive hypthoesis, the subproblems are optimal, so the result of dpTable[i][j] is optimal as well. Thus by induction, the dynamic programming table generated by the algorithm correctly stores the longest balanced subsequence length for every substring, and dpTable[0][n - 1] gives the final answer. QED.
## complexity 2:
The time complexity of this algorithm is O(n^3) since there are O(n^2) subproblems and up to O(n) splits per subproblem.