# Algorithm(s)

### Balanced Parentheses

Create an empty stack. For every character in the given string, the algoritm iterates through.

First, it checks to see if i matches an opening parenthesis or bracket. If so, it pushes i into the stack. If i matches a closing parentheses or bracket, it checks if the stack is otherwise empty, and returns false.

Then s.top() is preserved in var t, and s.pop() is called to remove it from the stack. The algorithm checks if c is a closing parentheses/bracket and if the top value (prior to popping) was an opening parentheses/bracket. If so, it returns false.

When the loop terminates, an empty stack is returned.

fun is_balanced(var str){

    stack s;
    
    for(int i = 0 i < str.len; i++){
        if(i == '(' || i == '[') s.push(i);
        else if(i == ')' || i == ']'){
            if(s.is_empty()) return; 
            t = s.top();
            s.pop();
            if(c == ')' && t != '(') return;
            if(c == ']' && t !+ '[') return;
        }
    }
    
    return s.empty();

}

### Longest Balanced Subsequence

The algorithm takes in a string s, and the size of the string, n. Then it creates dynamic array `arr[n][n]`, which represents the length of the longest balanced subsequence in the string. The algorithm begins from substring lenths of 2 -> n (for pairs), and evaluates, for each pair of j and k:

1) Whether to skip the first (`arr[j + 1][k]`) or last (`arr[j][k - 1]`) character, which involves taking the maximum of the two.

2) Whether the pairs match. If they match, the algorithm adds 2 to the inner substring of s from j + 1 --> k - 1 and takes the maximum of that.

Then the substring is split into left and right partitions, and the results are spliced through the maximum sum of either side.

Finally, the value of `arr[0][n-1]` is returned.

fun LBS(var s, var n){

    var arr[n][n];
    
    for(int i = 2; i <= n; i++){
        for(int j = 0; j + i - 1 < n; j++){
            int k = j + i - 1; 
            
            arr[j][k] = max(arr[j + 1][k], arr[j][k - 1]);

            if(s[j] == '(' && s[k] == ')' || s[j] == '[' && s[k] == ']'){
                arr[j][k] = max(arr[j][k], arr[j + 1][k - 1] + 2);
            }

            for(int a = j; a < l; a++){
                arr[j][k] = max(arr[j][k], arr[j][a] + arr[a + 1][k]);
            }
        }
    }

    return arr[0][n-1];

}

# Correctness Proof(s)

### Balanced Parentheses

**Base case:** n = 0, which means an empty string, which should automatically be balanced.

**Inductive hypothesis:** Assume that for all strings with a size of n <= k, the algorithm correctly evaluates whether they are balanced.

Now for the inductive step. Suppose we have a string s of a length larger than k (or k + 1).

**Case 1**: The first character is an '[', and the last character is an ']'. The first character is pushed and popped once the last character has been parsed. Then the substring contained inside the brackets is evaluated, and by inductive hypothesis, correctly checked. This means s is correctly balanced, so long as the inner substring is balanced.

**Case 2**: The given element is a concatenation of a string `ab`. The first character parsed is a. If a is balanced, then the stack is emptied out before b can be parsed. Then b is parsed with an empty stack, and by inductive hypothesis, both a and b are correctly evaluated. This means ab is correctly balanced only if a and b are both balanced.

**Case 3**: There is a mismatch in types, or the stack is empty and the algorithm attempts to pop from it, which returns false for unbalanced.

No further cases. The algorithm correctly classifies every string as balanced/unbalanced.

### Longest Balanced Subsequence

Base Case: if string `s` contains a substring with only one character, or that is empty.

Inductive hypothesis: Assume that for all strings of length less than k, the arr[a][b] correctly stores the longest balanced subsequences of `s`.

Suppose we have a substring s from j --> k of length l. Three cases exist:

Case 1: The very first character is not contained in the optimal solution, so the solution is narrowed down to j + 1 --> k.

Case 2: The last character is not contained in the optimal solution, so the solution is narrowed down to j --> k - 1.

Case 3: A matching pair is found between the first and last characters of the string.

Since each case takes the maximum solution (optimal), by inductive hypothesis, the smaller subproblems are correctly returned, which means that the larger problems must also be correct.

Thus, arr[j][k] is correctly evaluated.

# Time Complexities

### Balanced Parentheses
The complexity is O(N), since there is only one loop that iterates through the sequence.

### Longest Balanced Subsequence

The complexity is O(N^3), since it uses three seperate loops nested within each other.