Leetcode 87. Scramble String

 87. Scramble String

Hard, Dynamic Programming

We can scramble a string s to get a string t using the following algorithm:

1. If the length of the string is 1, stop.
2. If the length of the string is > 1, do the following:
   • Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
   • Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
   • Apply step 1 recursively on each of the two substrings x and y.

Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.

 

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Example 3:

Input: s1 = "a", s2 = "a"
Output: true

 

Constraints:

• s1.length == s2.length
• 1 <= s1.length <= 30
• s1 and s2 consist of lowercase English letters.

To solve the Scramble String problem, we can use dynamic programming (DP) to efficiently check if s2 is a scrambled string of s1. The problem can be understood as a recursive process where we split the strings at different positions and recursively check for possible scrambled configurations.

Approach:

We can define a recursive relationship where:

1. If s1 and s2 are identical, we return true.
2. If s1 and s2 have different characters, we return false.
3. If s1 and s2 can be divided into two substrings, we need to check two conditions:
   • No Swap: The first part of s1 can match the first part of s2 and the second part of s1 matches the second part of s2.
   • With Swap: The first part of s1 matches the second part of s2 and the second part of s1 matches the first part of s2.

Dynamic Programming Approach:

We can use memoization to store the results of subproblems to avoid redundant calculations. Specifically, we use a 3D DP table dp[i][j][len] where:

• i and j represent the starting indices of the substrings in s1 and s2.
• len is the length of the substring.
• dp[i][j][len] = true if the substring s1[i..i+len-1] can be scrambled to form s2[j..j+len-1].

Code:

public class Solution {
    public bool IsScramble(string s1, string s2) {
        if (s1.Length != s2.Length) return false; // If lengths are different, return false
        
        // Initialize the DP array for memoization
        int n = s1.Length;
        bool[,,] dp = new bool[n, n, n + 1];
        
        // Base case: when the substring lengths are 1, we only need to check the characters
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j, 1] = s1[i] == s2[j];
            }
        }
        
        // Check for all possible lengths of the substrings from 2 to n
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                for (int j = 0; j <= n - len; j++) {
                    for (int k = 1; k < len; k++) {
                        // No Swap case: s1[i..i+k-1] and s1[i+k..i+len-1] match s2[j..j+k-1] and s2[j+k..j+len-1]
                        if (dp[i, j, k] && dp[i + k, j + k, len - k]) {
                            dp[i, j, len] = true;
                            break;
                        }
                        
                        // With Swap case: s1[i..i+k-1] and s1[i+k..i+len-1] match s2[j+len-k..j+len-1] and s2[j..j+k-1]
                        if (dp[i, j + len - k, k] && dp[i + k, j, len - k]) {
                            dp[i, j, len] = true;
                            break;
                        }
                    }
                }
            }
        }

        // Return whether the entire string can be scrambled from s1 to s2
        return dp[0, 0, n];
    }
}

Explanation:

1. Base Case:

   • If the substrings have a length of 1, we simply check if the characters at those positions are equal, i.e., s1[i] == s2[j].

2. Filling the DP Table:

   • For each possible substring length (len), starting from 2 up to the length of the string n, we check all possible starting indices i and j for s1 and s2.
   • For each combination of substrings of length len, we try both the "no swap" and "with swap" conditions:
     • No Swap: The first k characters of s1 should match the first k characters of s2, and the remaining characters should also match.
     • With Swap: The first k characters of s1 should match the last k characters of s2, and the remaining characters should also match.

3. Final Result:

   • The result of whether s1 can be scrambled to s2 is stored in dp[0, 0, n] where n is the length of the strings.

Time Complexity:

• Time Complexity: $O(n^4)$, where n is the length of the strings. This is because we have 3 loops:
  • len loop runs from 2 to n.
  • i and j loops both run from 0 to n - len.
  • The inner loop (k) runs up to len.
• Space Complexity: $O(n^3)$ for the 3D DP table.

Example Walkthrough:

For the input:

s1 = "great", s2 = "rgeat"

• The algorithm recursively checks whether s1 can be scrambled to form s2 using both possible cases (with or without swap).
• It iterates through all possible substring splits and applies the scramble check recursively, storing results in the DP table for optimization.
• Ultimately, it returns true because s2 is indeed a scrambled string of s1.

Edge Cases:

• If the strings are identical (e.g., s1 = "a", s2 = "a"), the result is true.
• If the strings have different characters, the result is false (e.g., s1 = "abc", s2 = "def").
• The solution handles all edge cases within the given constraints (1 <= s1.length <= 30).

This dynamic programming solution is efficient and avoids redundant calculations by using memoization, making it suitable for the given constraints.

Another approach for solving the Scramble String problem that also involves recursion with memoization. The key idea in this approach is to use a recursive check for scramble relationships and utilize caching (memoization) to store already computed results for substrings, which helps in avoiding redundant recalculations.

Approach: Recursive with Memoization

In this approach, we define a recursive function to check if a substring of s1 can be scrambled to form a corresponding substring of s2. The recursion works as follows:

1. Base Case: If the two strings are identical, they are trivially scrambled (return true).
2. Character Frequency Check: If the two strings have different character frequencies (i.e., the same characters in a different order), then s2 cannot be a scrambled version of s1, and we return false.
3. Recursive Step:
   • We recursively divide the strings into two parts at each possible position k and check:
     • No Swap Case: Whether the first k characters of s1 can scramble to the first k characters of s2, and the remaining part of s1 can scramble to the remaining part of s2.
     • Swap Case: Whether the first k characters of s1 can scramble to the last k characters of s2, and the remaining part of s1 can scramble to the first part of s2.
4. Memoization: Store the results of the recursive calls for each substring combination to avoid redundant calculations.

Code:

public class Solution {
    public bool IsScramble(string s1, string s2) {
        // Memoization dictionary to store the results of subproblems
        Dictionary<string, bool> memo = new Dictionary<string, bool>();
        
        // Helper function for recursion with memoization
        return IsScrambleHelper(s1, s2, memo);
    }
    
    private bool IsScrambleHelper(string s1, string s2, Dictionary<string, bool> memo) {
        // If the two strings are identical, no need to scramble
        if (s1 == s2) return true;
        
        // If the lengths of the strings are different, they can't be scrambled
        if (s1.Length != s2.Length) return false;
        
        // Check if the result is already computed and stored in memo
        string key = s1 + " " + s2;
        if (memo.ContainsKey(key)) return memo[key];
        
        // If the two strings have different character counts, return false
        if (!IsSameCharacterCount(s1, s2)) {
            memo[key] = false;
            return false;
        }
        
        int n = s1.Length;
        for (int i = 1; i < n; i++) {
            // Check for both swap and no swap cases
            if ((IsScrambleHelper(s1.Substring(0, i), s2.Substring(0, i), memo) && 
                 IsScrambleHelper(s1.Substring(i), s2.Substring(i), memo)) || 
                (IsScrambleHelper(s1.Substring(0, i), s2.Substring(n - i), memo) && 
                 IsScrambleHelper(s1.Substring(i), s2.Substring(0, n - i), memo))) {
                memo[key] = true;
                return true;
            }
        }
        
        // Store the result in memo for future use
        memo[key] = false;
        return false;
    }
    
    // Helper function to check if both strings have the same character count
    private bool IsSameCharacterCount(string s1, string s2) {
        int[] count = new int[26];
        for (int i = 0; i < s1.Length; i++) {
            count[s1[i] - 'a']++;
            count[s2[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) return false;
        }
        return true;
    }
}

Explanation:

1. Memoization: A dictionary memo is used to store previously computed results for pairs of strings (s1, s2). This prevents redundant recursive calls and optimizes performance.
2. Base Case: If s1 and s2 are the same string, return true. If their lengths differ, return false.
3. Character Frequency Check: Before diving into recursion, we check if s1 and s2 contain the same characters in the same frequency using the IsSameCharacterCount helper function. If they don't, return false.
4. Recursive Case: We recursively check for both the "no swap" and "swap" cases by splitting the strings at every possible position i. If any of the cases return true, we conclude that s1 can be scrambled to form s2.
5. Memoization Storage: If we find that a pair of substrings can't be scrambled to each other, we store the result false in the memo dictionary. If we find that they can, we store true.

Time Complexity:

• Time Complexity: $O(n^3)$, where n is the length of the string. This is because:
  • Each pair of substrings is checked and stored in the memo dictionary.
  • For each substring pair, we check all possible splits.
  • The recursive calls involve checking the same substring pairs multiple times, which is why memoization helps to avoid redundant work.
• Space Complexity: $O(n^3)$ for the memo dictionary and the recursion stack.

Example Walkthrough:

For input s1 = "great" and s2 = "rgeat", the function proceeds as follows:

1. The algorithm checks if s1 and s2 have the same character counts.
2. It then recursively splits both strings at each possible position and checks both swap and non-swap configurations.
3. The recursion will eventually find that s1 can be scrambled into s2, and return true.

Edge Cases:

• If s1 and s2 are already equal, the algorithm returns true without further recursion.
• If s1 and s2 have different character sets, the result will be false immediately.

This approach is effective, and with memoization, the solution avoids recalculating the same results multiple times, leading to better performance compared to the naive recursive approach.

Leetcode 85. Maximal Rectangle

 85. Maximal Rectangle

Hard, Dynamic Programming

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

 

Constraints:

• rows == matrix.length
• cols == matrix[i].length
• 1 <= row, cols <= 200
• matrix[i][j] is '0' or '1'

To solve the Maximal Rectangle problem, we can use a combination of dynamic programming and a monotonic stack approach, which is efficient and works in $O(m \times n)$ time complexity, where m is the number of rows and n is the number of columns.

Approach:

1. Transform the problem into a histogram problem:

   • For each row, consider it as the base of a histogram where the heights of the bars are calculated by counting consecutive 1s vertically in the matrix. Essentially, the height of a bar at column j for row i is the number of consecutive 1s ending at that cell.
   • For every row, we will compute the histogram heights and then find the largest rectangle area that can be formed with those heights using a monotonic stack approach.

2. For each row:

   • Update the histogram of heights.
   • Calculate the maximal rectangle area for the updated histogram using a stack.

3. Use a monotonic stack to find the largest rectangle in the histogram:

   • For a given histogram, maintain a stack of column indices in increasing order of their heights. This allows us to efficiently calculate the largest rectangle area at each step.

Code:

public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
            return 0;
        }

        int m = matrix.Length;
        int n = matrix[0].Length;
        int[] heights = new int[n];
        int maxArea = 0;

        // Iterate through each row of the matrix
        for (int i = 0; i < m; i++) {
            // Update the heights array based on the current row
            for (int j = 0; j < n; j++) {
                // If the current cell is '1', increase the height; otherwise, reset to 0
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }

            // Calculate the maximum area for the current histogram (heights array)
            maxArea = Math.Max(maxArea, MaxHistogramArea(heights));
        }

        return maxArea;
    }

    private int MaxHistogramArea(int[] heights) {
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        int n = heights.Length;

        // Iterate through the heights array and process each bar in the histogram
        for (int i = 0; i <= n; i++) {
            // While there are bars in the stack and the current bar is shorter than the top bar in the stack
            while (stack.Count > 0 && (i == n || heights[stack.Peek()] > heights[i])) {
                int h = heights[stack.Pop()];  // Get the height of the bar
                int width = stack.Count > 0 ? i - stack.Peek() - 1 : i;  // Calculate the width
                maxArea = Math.Max(maxArea, h * width);  // Update the maximum area
            }
            stack.Push(i);  // Push the current index onto the stack
        }

        return maxArea;
    }
}

Explanation:

1. Updating the histogram (heights array):

   • For each row, we traverse all columns. If the value is 1, we increase the corresponding value in the heights array. If the value is 0, we reset the corresponding height to 0 because the rectangle cannot extend further down.

2. Monotonic stack approach (MaxHistogramArea):

   • The function MaxHistogramArea calculates the largest rectangle area that can be formed from the histogram represented by the heights array.
   • We use a stack to store column indices in increasing order of their heights. For each column, if the current height is smaller than the height of the column at the top of the stack, we pop the stack and calculate the area of the rectangle formed with the popped height. The width of the rectangle is determined by the difference between the current index and the index of the new top of the stack.
   • This ensures that we can calculate the largest rectangle area in linear time $O(n)$ for each row.

3. Final Result:

   • For each row, after updating the heights array, we calculate the maximum rectangle area using the MaxHistogramArea function and update the global maxArea.

Time Complexity:

• Time Complexity: $O(m \times n)$, where m is the number of rows and n is the number of columns. We process each element in the matrix once and calculate the maximal rectangle for each histogram in linear time $O(n)$.
• Space Complexity: $O(n)$ for the heights array and the stack.

Example Walkthrough:

For the input:

matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]

• After processing the first row, the heights array becomes [1, 0, 1, 0, 0].
• After processing the second row, the heights array becomes [2, 0, 2, 1, 1].
• After processing the third row, the heights array becomes [3, 1, 3, 2, 2].
• After processing the fourth row, the heights array becomes [4, 0, 0, 3, 0].

The maximum area found is 6 by considering the rectangle of width 3 and height 2 in the third row.

Edge Cases:

1. If the matrix is empty, the result is 0.
2. If all elements are 0, the result is 0.
3. If the matrix contains only 1s, the area is simply the entire matrix area.
4. The solution handles matrices of varying sizes and row/column distributions efficiently.

This approach is optimal and works well for the given constraints.