Longest Valid Parentheses

Given a string containing only '(' and ')', find the length of the longest valid (well-formed and contiguous) parentheses substring.

Dynamic Programming Solution

Define dp[i] as the length of the longest valid parentheses ending at position i. To each character at index i:

• If s[i] is '(', set dp[i] = 0
• If s[i] is ')', check the character at position i - dp[i-1] - 1 (denoted as prev):
  • If prev < 0 or s[prev] is ')', set dp[i] = 0
  • If s[prev] is '(', update dp[i] = dp[i-1] + 2 + dp[prev-1]

The answer is the maximum value in the dp array.

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length(), maxLen = 0;
        vector<int> dp(n, 0);
        
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                int prev = i - dp[i-1] - 1;
                if (prev >= 0 && s[prev] == '(') {
                    dp[i] = dp[i-1] + 2;
                    if (prev > 0) {
                        dp[i] += dp[prev-1];
                    }
                    maxLen = max(maxLen, dp[i]);
                }
            }
        }
        return maxLen;
    }
};

Trapping Rain Water

Given n non-neagtive integers representing an elevasion map where each bar has width 1, compute how much water it can trap after raining.

Dynamic Programming Approach

Calculate left and right maximum heights for each position, then determine water capacity at each index.

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        
        vector<int> leftMax(n), rightMax(n);
        
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = max(leftMax[i-1], height[i]);
        }
        
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = max(rightMax[i+1], height[i]);
        }
        
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += min(leftMax[i], rightMax[i]) - height[i];
        }
        
        return water;
    }
};

Two Pointer Technique

Use left and right pointers to track maximum heights from both ends, calculating water contribution as pointers move.

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        int totalWater = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    totalWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    totalWater += rightMax - height[right];
                }
                right--;
            }
        }
        
        return totalWater;
    }
};

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*' where:

• '?' matches any single character
• '*' matches any sequence of characters (including empty sequence)

The pattern must match the entire input string.

Dynamic Programming Solution

Use dynamic programming to track matching states between pattern and string.

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        
        for (int i = 1; i <= n; i++) {
            if (p[i-1] == '*') {
                dp[i][0] = dp[i-1][0];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[i-1] == s[j-1] || p[i-1] == '?') {
                    dp[i][j] = dp[i-1][j-1];
                } else if (p[i-1] == '*') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            }
        }
        
        return dp[n][m];
    }
};