Leetcode Problem 32 - Longest Valid Parentheses

32. Longest Valid Parentheses

Hard, Dynamic Programming

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = "(()"

Output: 2

Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"

Output: 4

Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""

Output: 0

 

Constraints:

• 0 <= s.length <= 3 * 10⁴

s[i] is '(', or ')'.

SOLUTION

To solve the Longest Valid Parentheses problem, we need to determine the maximum length of well-formed parentheses substrings. Here are the possible approaches:

---

Plan:

1. Stack-based Approach:

   • Use a stack to track indices of unmatched parentheses.
   • Push -1 to the stack initially to act as a base index for valid substrings.
   • Iterate through the string:
     • Push the index when encountering an opening parenthesis (.
     • When encountering a closing parenthesis ):
       • Pop the top of the stack.
       • If the stack is empty, push the current index.
       • Otherwise, calculate the valid substring length as the difference between the current index and the top of the stack.
   • Keep track of the maximum valid substring length.

2. Dynamic Programming:

   • Use a DP array dp where dp[i] represents the length of the longest valid substring ending at index i.
   • Traverse the string:
     • If s[i] is ) and the preceding character forms a valid pair (e.g., s[i-1] is ():
       • Add 2 to the value of dp[i-2] (or 0 if i-2 is out of bounds).
     • If s[i] is ) and there’s a valid substring ending before a matching (:
       • Extend the valid length by considering the substring length before the matching (.
   • Keep track of the maximum value in the dp array.

3. Two-Pointer Traversal:

   • Use two counters, left and right, to traverse the string twice:
     • From left to right, count ( and ).
       • If they are equal, calculate the length.
       • If right > left, reset the counters.
     • From right to left, count ) and (.
       • If they are equal, calculate the length.
       • If left > right, reset the counters.
   • Keep track of the maximum length.

---

Implementation (Stack-based Approach):

public class Solution {
    public int LongestValidParentheses(string s) {
        Stack<int> stack = new Stack<int>();
        stack.Push(-1); // Base index for valid substrings
        int maxLength = 0;

        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push(i); // Push index of '('
            } else {
                stack.Pop(); // Pop for ')'
                if (stack.Count == 0) {
                    stack.Push(i); // Push current index as base
                } else {
                    maxLength = Math.Max(maxLength, i - stack.Peek());
                }
            }
        }

        return maxLength;
    }
}

---

Implementation (Dynamic Programming):

public class Solution {
    public int LongestValidParentheses(string s) {
        int n = s.Length;
        if (n == 0) return 0;

        int[] dp = new int[n];
        int maxLength = 0;

        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLength = Math.Max(maxLength, dp[i]);
            }
        }

        return maxLength;
    }
}

---

Implementation (Two-Pointer Traversal):

public class Solution {
    public int LongestValidParentheses(string s) {
        int left = 0, right = 0, maxLength = 0;

        // Left to right
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') left++;
            else right++;

            if (left == right) {
                maxLength = Math.Max(maxLength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }

        // Right to left
        left = right = 0;
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == ')') right++;
            else left++;

            if (left == right) {
                maxLength = Math.Max(maxLength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }

        return maxLength;
    }
}

---

Complexity Analysis:

1. Stack-based Approach:

   • Time Complexity: $O(n)$ — Single traversal of the string.
   • Space Complexity: $O(n)$ — Stack space.

2. Dynamic Programming:

   • Time Complexity: $O(n)$ — Single traversal of the string.
   • Space Complexity: $O(n)$ — DP array.

3. Two-Pointer Traversal:

   • Time Complexity: $O(n)$ — Two traversals of the string.
   • Space Complexity: $O(1)$ — Constant space.

---

Example Outputs:

Example 1:

• Input: "(()"
• Output: 2

Example 2:

• Input: ")()())"
• Output: 4

Example 3:

• Input: ""
• Output: 0

Leetcode Problem 799 - Champagne Tower

799.Champagne Tower

Medium, Dynamic Programming

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100^th row.  Each glass holds one cup of champagne.

Then, some champagne is poured into the first glass at the top.  When the topmost glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it.  When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on.  (A glass at the bottom row has its excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full.  After two cups of champagne are poured, the two glasses on the second row are half full.  After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now.  After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

Now after pouring some non-negative integer cups of champagne, return how full the j^th glass in the i^th row is (both i and j are 0-indexed.)

 

Example 1:

Input: poured = 1, query_row = 1, query_glass = 1

Output: 0.00000

Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:

Input: poured = 2, query_row = 1, query_glass = 1

Output: 0.50000

Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

Example 3:

Input: poured = 100000009, query_row = 33, query_glass = 17

Output: 1.00000

 

Constraints:

• 0 <= poured <= 10⁹
• 0 <= query_glass <= query_row < 100

SOLUTION

To solve the Champagne Tower problem, we need to simulate the flow of champagne through the glasses in the pyramid. Here's how we can approach the solution:

---

Plan:

1. Understand the Flow:

   • Each glass can hold up to 1 cup of champagne.
   • Any excess champagne is split equally between the two glasses directly below it in the next row.
   • A glass does not receive champagne from glasses other than the one(s) directly above it.

2. Simulation Using a 2D Array:

   • Use a 2D array tower where tower[i][j] represents the amount of champagne in the j-th glass of the i-th row.
   • Start with tower[0][0] = poured.
   • Iterate row by row, calculating the overflow for each glass and distributing it to the glasses in the next row.

3. Return the Result:

   • If the champagne in the target glass (tower[query_row][query_glass]) is less than or equal to 1, return it.
   • Otherwise, return 1, as a glass can only be full.

---

Implementation:

public class Solution {
    public double ChampagneTower(int poured, int query_row, int query_glass) {
        // Initialize a 2D array to simulate the champagne tower
        double[][] tower = new double[query_row + 2][];
        for (int i = 0; i < tower.Length; i++) {
            tower[i] = new double[i + 1];
        }

        // Pour champagne into the topmost glass
        tower[0][0] = poured;

        // Simulate the champagne flow row by row
        for (int row = 0; row <= query_row; row++) {
            for (int col = 0; col <= row; col++) {
                // If there is overflow
                if (tower[row][col] > 1) {
                    double overflow = (tower[row][col] - 1) / 2.0;
                    tower[row + 1][col] += overflow;       // Left glass in next row
                    tower[row + 1][col + 1] += overflow;   // Right glass in next row
                    tower[row][col] = 1;                  // Current glass capped at 1
                }
            }
        }

        // Return the amount in the target glass
        return Math.Min(1, tower[query_row][query_glass]);
    }

    public static void Main(string[] args) {
        var solution = new Solution();
        Console.WriteLine(solution.ChampagneTower(1, 1, 1)); // Output: 0.00000
        Console.WriteLine(solution.ChampagneTower(2, 1, 1)); // Output: 0.50000
        Console.WriteLine(solution.ChampagneTower(100000009, 33, 17)); // Output: 1.00000
    }
}

---

Explanation of Code:

1. 2D Array Initialization:

   • The array tower is a jagged array, where each row can have a different number of glasses.

2. Flow Simulation:

   • Start from the top row and move down.
   • For each glass, if it contains more than 1 cup, calculate the overflow and distribute it equally to the two glasses below it.
   • Cap the current glass's value at 1 since it cannot hold more than 1 cup.

3. Return the Result:

   • The champagne amount in tower[query_row][query_glass] is capped at 1 if it's more than 1, as a glass cannot hold more than 1 cup.

---

Complexity:

• Time Complexity: $O(\text{query\_row}^2)$
  • Each row processes all the glasses up to that row, resulting in a total of approximately $\frac{\text{query\_row}(\text{query\_row} + 1)}{2}$ operations.
• Space Complexity: $O(\text{query\_row}^2)$
  • We use a 2D array to store champagne levels for all glasses up to query_row.

---

Example Outputs:

Example 1:

• Input: poured = 1, query_row = 1, query_glass = 1
• Output: 0.00000
• Explanation: Only the top glass is full; no champagne flows to the second row.

Example 2:

• Input: poured = 2, query_row = 1, query_glass = 1
• Output: 0.50000
• Explanation: The top glass overflows, and the two glasses in the second row each get 0.5 cups.

Example 3:

• Input: poured = 100000009, query_row = 33, query_glass = 17
• Output: 1.00000
• Explanation: The glass is completely full due to the large amount of champagne poured.

 

LeetCode Problem 792 - Number of Matching Subsequences

   792. Number of Matching Subsequences

Medium, Dynamic Programming

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

 

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]

Output: 3

Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]

Output: 2

 

Constraints:

• 1 <= s.length <= 5 * 10⁴
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

 

SOLUTION:

To solve this problem, we need to efficiently check how many strings in the words array are subsequences of the string s. A subsequence is defined as a sequence of characters that appear in the same order as in the original string s, but not necessarily consecutively.

Plan:

1. Optimize the Matching Process: Instead of checking each word in words against s character by character (which would be inefficient), we can use a bucket approach:

   • Group the words based on their first character.
   • For each character in s, process all words waiting for that character.

2. Iterate Through s:

   • As we iterate through the characters of s, we advance the matching process for words waiting on that character.

3. Use Buckets:

   • Maintain a dictionary where each key is a character, and the value is a list of iterators. Each iterator represents a word and its current position in the matching process.

4. Count Matches:

   • When a word's iterator reaches the end, it means the word is a subsequence of s.

Implementation:

using System;
using System.Collections.Generic;

public class Solution {
    public int NumMatchingSubseq(string s, string[] words) {
        // Dictionary to hold buckets of words grouped by the current character they are waiting for
        var waiting = new Dictionary<char, Queue<IEnumerator<char>>>();
        
        // Initialize the dictionary with all lowercase letters
        for (char c = 'a'; c <= 'z'; c++) {
            waiting[c] = new Queue<IEnumerator<char>>();
        }

        // Populate the buckets based on the first character of each word
        foreach (var word in words) {
            var iterator = word.GetEnumerator();
            if (iterator.MoveNext()) {
                waiting[iterator.Current].Enqueue(iterator);
            }
        }

        int count = 0;

        // Iterate through characters of the string `s`
        foreach (char c in s) {
            var bucket = waiting[c]; // Get the bucket for the current character
            int size = bucket.Count;

            for (int i = 0; i < size; i++) {
                var iterator = bucket.Dequeue(); // Get the next word's iterator
                if (iterator.MoveNext()) {
                    waiting[iterator.Current].Enqueue(iterator); // Move to the next character
                } else {
                    count++; // Word is a subsequence
                }
            }
        }

        return count;
    }

    public static void Main(string[] args) {
        var solution = new Solution();
        Console.WriteLine(solution.NumMatchingSubseq("abcde", new string[] { "a", "bb", "acd", "ace" })); // Output: 3
        Console.WriteLine(solution.NumMatchingSubseq("dsahjpjauf", new string[] { "ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax" })); // Output: 2
    }
}

Explanation of Code:

1. Dictionary for Buckets:

   • waiting is a dictionary where keys are characters ('a' to 'z'), and values are queues of iterators for words waiting on that character.

2. Iterating Over s:

   • For each character in s, process all words waiting for it.
   • If the iterator can move to the next character, enqueue it into the bucket for the next character.
   • If the iterator is exhausted, increment the match count.

3. Efficiency:

   • Each word is processed exactly once, and each character in s is processed once.
   • Total complexity: $O(L + M)$, where $L$ is the total length of all words in words, and $M$ is the length of s.

Example Outputs:

Example 1:

• s = "abcde", words = ["a", "bb", "acd", "ace"]
• Words "a", "acd", and "ace" are subsequences of "abcde".
• Output: 3

Example 2:

• s = "dsahjpjauf", words = ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]
• Words "ahjpjau" and "ja" are subsequences of "dsahjpjauf".
• Output: 2

Leetcode Problem 42 - Trapping RainWater

 42. Trapping RainWater

Hard, Dynamic Programming

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 10⁴
• 0 <= height[i] <= 10⁵

 To solve the Trapping Rain Water problem, we can calculate the amount of water trapped above each bar in the elevation map. Below are three approaches:

---

Approaches:

1. Brute Force:

   • For each bar, calculate the maximum height of bars to the left and right.
   • Water above the current bar is determined by the minimum of these two heights minus the height of the current bar.

2. Dynamic Programming:

   • Precompute the maximum height of bars to the left (leftMax) and right (rightMax) for each index.
   • For each bar, the water trapped is the difference between the minimum of leftMax and rightMax and the height of the bar.

3. Two Pointers:

   • Use two pointers (left and right) and two variables to keep track of the maximum heights from the left and right.
   • Move the pointers inward, adding trapped water based on the smaller height.

---

Implementation (Two Pointers Approach):

The two-pointer approach is efficient and works in $O(n)$ time and $O(1)$ space.

public class Solution {
    public int Trap(int[] height) {
        if (height == null || height.Length == 0) return 0;

        int left = 0, right = height.Length - 1;
        int leftMax = 0, rightMax = 0, waterTrapped = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    waterTrapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    waterTrapped += rightMax - height[right];
                }
                right--;
            }
        }

        return waterTrapped;
    }
}

---

Implementation (Dynamic Programming Approach):

public class Solution {
    public int Trap(int[] height) {
        if (height == null || height.Length == 0) return 0;

        int n = height.Length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.Max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.Max(rightMax[i + 1], height[i]);
        }

        int waterTrapped = 0;
        for (int i = 0; i < n; i++) {
            waterTrapped += Math.Min(leftMax[i], rightMax[i]) - height[i];
        }

        return waterTrapped;
    }
}

---

Implementation (Brute Force Approach):

public class Solution {
    public int Trap(int[] height) {
        if (height == null || height.Length == 0) return 0;

        int n = height.Length, waterTrapped = 0;
        for (int i = 0; i < n; i++) {
            int leftMax = 0, rightMax = 0;

            // Find the maximum height to the left of the current bar
            for (int j = 0; j <= i; j++) {
                leftMax = Math.Max(leftMax, height[j]);
            }

            // Find the maximum height to the right of the current bar
            for (int j = i; j < n; j++) {
                rightMax = Math.Max(rightMax, height[j]);
            }

            waterTrapped += Math.Min(leftMax, rightMax) - height[i];
        }

        return waterTrapped;
    }
}

---

Complexity Analysis:

1. Brute Force:

   • Time Complexity: $O(n^2)$ — Two nested loops for left and right max calculations.
   • Space Complexity: $O(1)$ — No extra space used.

2. Dynamic Programming:

   • Time Complexity: $O(n)$ — Precomputing left and right max arrays and a single traversal.
   • Space Complexity: $O(n)$ — Left and right max arrays.

3. Two Pointers:

   • Time Complexity: $O(n)$ — Single traversal of the array.
   • Space Complexity: $O(1)$ — Only a few variables used.

---

Example Outputs:

Example 1:

• Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
• Output: 6

Example 2:

• Input: height = [4,2,0,3,2,5]
• Output: 9

 

Leetcode Problem 5 - Longest Palindromic Substring -

Longest Palindromic Substring

Problem Statement

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"

Output: "bab"

Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"

Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consists of only digits and English letters.

Approaches

Expand Around Center Approach

Explanation:

• Every palindrome is centered at either a single character or a pair of characters.
• Expand around each center to find the longest palindrome, checking both odd-length and even-length cases.
• This approach is efficient with O(n^2) time complexity and O(1) space complexity.

public class Solution {
    public string LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s) || s.Length < 1) return "";

        int start = 0, end = 0;

        for (int i = 0; i < s.Length; i++) {
            int len1 = ExpandFromCenter(s, i, i);     // Odd-length palindromes
            int len2 = ExpandFromCenter(s, i, i + 1); // Even-length palindromes
            int len = Math.Max(len1, len2);

            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.Substring(start, end - start + 1);
    }

    private int ExpandFromCenter(string s, int left, int right) {
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1; // Length of the palindrome
    }
}

Dynamic Programming Approach

Explanation:

• Use a 2D table dp where dp[i][j] is true if the substring s[i...j] is a palindrome.
• Transition:
  • dp[i][j] = true if s[i] == s[j] and dp[i+1][j-1] is true (or if the length is less than 3).
• Track the longest palindrome during the process.
• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

public class Solution {
    public string LongestPalindrome(string s) {
        if (s == null || s.Length == 0) return "";

        int n = s.Length;
        bool[,] dp = new bool[n, n];
        int start = 0, maxLength = 0;

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    dp[i, j] = (len == 1 || len == 2) || dp[i + 1, j - 1];
                    if (dp[i, j] && len > maxLength) {
                        start = i;
                        maxLength = len;
                    }
                }
            }
        }

        return s.Substring(start, maxLength);
    }
}

Brute Force Approach

Explanation:

• Check all substrings of s to determine if they are palindromic.
• This is inefficient for large input sizes.
• Time Complexity: O(n^3)
• Space Complexity: O(1)

public class Solution {
    public string LongestPalindrome(string s) {
        if (s == null || s.Length == 0) return "";

        string longest = "";

        for (int i = 0; i < s.Length; i++) {
            for (int j = i; j < s.Length; j++) {
                if (IsPalindrome(s, i, j) && (j - i + 1 > longest.Length)) {
                    longest = s.Substring(i, j - i + 1);
                }
            }
        }

        return longest;
    }

    private bool IsPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }
}

Complexity Analysis

Expand Around Center:

• Time Complexity: O(n^2) — Each center expansion takes O(n), and there are O(n) centers.
• Space Complexity: O(1).

Dynamic Programming:

• Time Complexity: O(n^2) — Filling the DP table.
• Space Complexity: O(n^2) — Storing the DP table.

Brute Force:

• Time Complexity: O(n^3) — Checking all substrings and validating each palindrome.
• Space Complexity: O(1).

Example Outputs

Example 1:

Input: s = "babad"

Output: "bab" or "aba"

Example 2:

Input: s = "cbbd"

Output: "bb"

Example 3:

Input: s = ""

Output: ""

Example 4:

Input: s = "a"

Output: "a"

Leetcode Problem 10 - Regular Expression Matching

10. RegularExpression Matching

Hard, Dynamic Programming

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

• '.' Matches any single character.​​​​
• '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

 

Example 1:

Input: s = "aa", p = "a"

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"

Output: true

Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"

Output: true

Explanation: ".*" means "zero or more (*) of any character (.)".

 

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

To solve the Regular Expression Matching problem, we need to use Dynamic Programming (DP) to handle the pattern p and the string s effectively, especially considering the wildcard characters . and *.

---

Approach:

1. Dynamic Programming Table:

We define a 2D DP table dp[i][j]:

• dp[i][j] indicates whether the first i characters of s match the first j characters of p.
• Base Case:
  • dp[0][0] = true — An empty string matches an empty pattern.
  • dp[0][j] — Depends on whether p[j-1] is * and if the preceding pattern allows a match.
• Transition:
  • If p[j-1] is a regular character or .:
    • dp[i][j] = dp[i-1][j-1] if s[i-1] == p[j-1] or p[j-1] == '.'.
  • If p[j-1] is *:
    • dp[i][j] = dp[i][j-2] (zero occurrence of the preceding character in p).
    • dp[i][j] = dp[i-1][j] (one or more occurrences, if s[i-1] == p[j-2] or p[j-2] == '.').

2. Algorithm:

• Construct a DP table of size (s.Length + 1) x (p.Length + 1).
• Fill the table iteratively based on the above rules.
• The result is stored in dp[s.Length][p.Length].

---

Implementation:

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] dp = new bool[m + 1, n + 1];

        // Base case: empty string matches empty pattern
        dp[0, 0] = true;

        // Handle patterns with '*'
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 2]; // '*' acts as zero occurrences
            }
        }

        // Fill the DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                    dp[i, j] = dp[i - 1, j - 1];
                } else if (p[j - 1] == '*') {
                    // '*' acts as zero occurrences or one/more occurrences
                    dp[i, j] = dp[i, j - 2] || 
                               (dp[i - 1, j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                }
            }
        }

        // The result is in the bottom-right cell of the table
        return dp[m, n];
    }
}

---

Explanation of Code:

1. Initialization:

   • dp[0][0] is true because an empty string matches an empty pattern.
   • For patterns like a*, a*b*, etc., set dp[0][j] based on whether * can eliminate its preceding character.

2. Filling the Table:

   • Match characters directly if they are the same or if the pattern has ..
   • Handle * by either ignoring the preceding character (dp[i][j-2]) or using it (dp[i-1][j]).

3. Result:

   • The result is found in dp[s.Length][p.Length].

---

Complexity Analysis:

1. Time Complexity:

   • $O(m \times n)$, where $m = s.Length$ and $n = p.Length$.

2. Space Complexity:

   • $O(m \times n)$ for the DP table.
   • Can be optimized to $O(n)$ using a rolling array.

---

Example Outputs:

Example 1:

• Input: s = "aa", p = "a"
• Output: false

Example 2:

• Input: s = "aa", p = "a*"
• Output: true

Example 3:

• Input: s = "ab", p = ".*"
• Output: true

Example 4:

• Input: s = "mississippi", p = "mis*is*p*."
• Output: false

This solution ensures correctness for all edge cases and adheres to the problem's constraints.

 

Leetcode Problem 22 - GenerateParentheses

 22. GenerateParentheses

Medium, Dynamic Programming

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1

Output: ["()"]

 

Constraints:

• 1 <= n <= 8

 

 The problem of generating well-formed parentheses can be solved using Backtracking. The idea is to build the parentheses combinations recursively, ensuring that we only add valid parentheses at each step.

---

Approach:

1. Backtracking:

   • Start with an empty string.
   • Maintain counts for the number of open and close parentheses used.
   • Only add:
     • An open parenthesis if the count of open parentheses is less than $n$.
     • A close parenthesis if the count of close parentheses is less than the count of open parentheses (to ensure the string remains valid).
   • Once both open and close parentheses are used $n$ times, add the string to the result.

2. Algorithm:

   • Use a helper function Backtrack that takes the current string, counts of open and close parentheses, and $n$ as arguments.
   • Recursively explore all valid combinations.
   • Stop the recursion when both open and close counts reach $n$.

---

Implementation:

public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        List<string> result = new List<string>();
        Backtrack(result, "", 0, 0, n);
        return result;
    }

    private void Backtrack(List<string> result, string current, int open, int close, int max) {
        // If the current string is complete, add it to the result
        if (current.Length == max * 2) {
            result.Add(current);
            return;
        }

        // Add an open parenthesis if the count is less than max
        if (open < max) {
            Backtrack(result, current + "(", open + 1, close, max);
        }

        // Add a close parenthesis if it doesn't exceed the number of open ones
        if (close < open) {
            Backtrack(result, current + ")", open, close + 1, max);
        }
    }
}

---

Explanation of Code:

1. Base Case:

   • When the length of the current string is $2 \times n$, it is a valid combination and added to the result list.

2. Recursive Case:

   • Add ( if the number of open parentheses used is less than $n$.
   • Add ) if the number of close parentheses is less than the number of open parentheses.

3. Termination:

   • The recursion stops when all valid combinations are generated.

---

Complexity Analysis:

1. Time Complexity:

   • Each valid combination is of length $2 \times n$.
   • There are $C_n = \frac{(2n)!}{(n+1)! \cdot n!}$ (Catalan numbers) valid combinations.
   • Hence, the complexity is approximately $O(4^n / \sqrt{n})$.

2. Space Complexity:

   • The recursion stack can go as deep as $2n$, so $O(2n) = O(n)$.

---

Example Outputs:

Example 1:

• Input: n = 3
• Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Example 2:

• Input: n = 1
• Output: ["()"]

This implementation generates all well-formed parentheses combinations efficiently while ensuring correctness through backtracking.

Leetcode Problem 44 - Wildcard Matching

Wildcard Matching

Difficulty: Hard

Problem Statement

Given an input string s and a pattern p, implement wildcard matching with support for the following:

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

The match should cover the entire input string, not just a partial match.

Examples

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence of characters.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but 'a' does not match 'b'.

Constraints

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?', or '*'.

---

Approach: Dynamic Programming (Bottom-Up)

To efficiently solve this problem, we use Dynamic Programming (DP).

Step 1: Define the DP Table

We create a 2D table dp[i][j], where:

• dp[i][j] = true if the first i characters of s match the first j characters of p.

Why DP?

• '*' can match multiple characters, requiring us to track results of smaller subproblems.
• A table-based approach avoids redundant calculations.

Step 2: Base Cases

1. Empty string matches an empty pattern:
   • dp[0][0] = true (Empty pattern matches an empty string).
2. Handling patterns with leading '*':
   • If p[j-1] == '*', then dp[0][j] = dp[0][j-1] (i.e., '*' behaves as an empty match).

Step 3: Filling the DP Table

We iterate through s and p, applying these rules:

1. Character Matches (s[i-1] == p[j-1] or p[j-1] == '?')
   • If characters match or p[j-1] == '?', then:

     dp[i][j] = dp[i-1][j-1];
     

2. Handling '*' (Matches Any Sequence)
   • '*' can:
     • Match zero characters → dp[i][j] = dp[i][j-1]
     • Match one or more characters → dp[i][j] = dp[i-1][j]
   • Formula:

     dp[i][j] = dp[i-1][j] || dp[i][j-1];
     

---

C# Implementation

using System;

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] dp = new bool[m + 1, n + 1];

        // Base case: Empty string matches empty pattern
        dp[0, 0] = true;

        // Fill first row for patterns with '*'
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 1];  // '*' matches empty sequence
            }
        }

        // Fill DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {
                    dp[i, j] = dp[i - 1, j - 1];  // Match single character or '?'
                } else if (p[j - 1] == '*') {
                    dp[i, j] = dp[i - 1, j] || dp[i, j - 1];  // '*' matches one or more OR empty
                }
            }
        }

        return dp[m, n];
    }
}

// Example Usage
class Program {
    static void Main() {
        Solution solution = new Solution();
        
        Console.WriteLine(solution.IsMatch("aa", "a"));       // false
        Console.WriteLine(solution.IsMatch("aa", "*"));       // true
        Console.WriteLine(solution.IsMatch("cb", "?a"));      // false
        Console.WriteLine(solution.IsMatch("adceb", "*a*b")); // true
        Console.WriteLine(solution.IsMatch("acdcb", "a*c?b"));// false
    }
}

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
DP Table	O(m × n)	O(m × n)
Optimized DP (1D Array)	O(m × n)	O(n)

---

Optimized Approach (Space Reduction)

Instead of a 2D table, we can use two 1D arrays (current and previous row), reducing space from O(m × n) to O(n).

---

Example Walkthrough

Example 1: s = "aa", p = "a"

	a
a	T
a	F

Output: false

Example 2: s = "aa", p = "*"

	*
a	T
a	T

Output: true

---

Edge Cases Considered

✅ Empty s or p
✅ Pattern with multiple '*'
✅ Pattern with '?'
✅ No wildcards

---

Summary

✅ DP Table efficiently stores subproblem results.
✅ Handles '*' and '?' effectively.
✅ Optimized Space Approach reduces memory usage.

This C# solution ensures efficient wildcard pattern matching! 🚀

Leetcode Problem 45 - Jump Game II

 45. Jump Game II

Medium, Dynamic Programming

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

The Jump Game II problem can be solved efficiently using a Greedy Algorithm. The goal is to determine the minimum number of jumps needed to reach the last index.

---

Approach:

1. Greedy Approach:
   • Track the farthest position that can be reached in the current jump.
   • Use a variable to count the current jumps.
   • At each step, if the current index matches the end of the current range of the jump, increment the jump count and update the range to the farthest position reached so far.

---

Steps:

1. Initialize Variables:

   • jumps: Counts the number of jumps required (start with 0).
   • current_end: Tracks the end of the current jump range.
   • farthest: Tracks the farthest index reachable within the current range.

2. Iterate Through the Array:

   • Update farthest for each index based on the jump capability from that index.
   • If the current index reaches current_end, it means the current jump ends, so increment the jump count and update current_end to farthest.

3. Stop Early:

   • Once the current_end reaches or exceeds the last index, return the number of jumps.

---

Implementation:

public class Solution {
    public int Jump(int[] nums) {
        int n = nums.Length;
        if (n == 1) return 0; // No jumps needed if there's only one element
        
        int jumps = 0, currentEnd = 0, farthest = 0;
        
        for (int i = 0; i < n - 1; i++) {
            // Update the farthest point reachable
            farthest = Math.Max(farthest, i + nums[i]);
            
            // If we reach the end of the current jump range
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                
                // If we've reached or passed the last index, stop early
                if (currentEnd >= n - 1) break;
            }
        }
        
        return jumps;
    }
}

---

Explanation of Code:

1. Initialization:

   • jumps is initially 0 because no jumps have been made.
   • currentEnd is the range limit for the current jump.
   • farthest tracks the maximum reachable index.

2. Iterating Through nums:

   • Update farthest to be the maximum reachable index from the current position.
   • If i == currentEnd, it means the current jump has reached its range limit:
     • Increment the jump count (jumps++).
     • Update currentEnd to farthest.

3. Termination:

   • As soon as currentEnd reaches or exceeds n - 1, the loop ends early.

---

Complexity Analysis:

1. Time Complexity:

   • $O(n)$: Single traversal of the array.

2. Space Complexity:

   • $O(1)$: Only a few variables are used.

---

Examples:

Example 1:

• Input: nums = [2,3,1,1,4]
• Steps:
  1. Jump to index 1 (farthest: 4).
  2. Jump directly to the last index.
• Output: 2.

Example 2:

• Input: nums = [2,3,0,1,4]
• Steps:
  1. Jump to index 1 (farthest: 4).
  2. Jump directly to the last index.
• Output: 2.

This greedy algorithm ensures that the solution is efficient and handles large inputs within constraints.