33. Test Your Knowledge (Hard)

Grokking Interview Pattern Interview

Word count: 1.4kReading time: 8 min

 2024/06/02 

Longest Valid Parentheses

Problem Statement

You are given a string containing just the characters ‘(‘ and ‘)’. Your task is to find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(())"
Expected Output: 4
Justification: The entire string is a valid parentheses substring.

Example 2:

Input: ")()())"
Expected Output: 4
Justification: The longest valid parentheses substring is "()()".

Example 3:

Input: "(()"
Expected Output: 2
Justification: The longest valid parentheses substring is "()".

Constraints:

0 <= s.length <= 3 * 10^4
s[i] is ‘(‘, or ‘)’.

Solution

Understanding the Problem:
- The problem involves finding the longest sequence of valid parentheses.
- A stack data structure can be used to keep track of the indices of the invalid parentheses.
Approach:
- Initialize a stack and push -1 onto it as a marker for the base.
- Iterate through the string and for each character:
  - If it is '(', push its index onto the stack.
  - If it is ')', pop an element from the stack.
    - If the stack is not empty, calculate the length of the valid parentheses substring by subtracting the current index with the top of the stack.
    - If the stack is empty, push the current index onto the stack to serve as the new base marker.
Why This Approach Will Work:
- The stack keeps track of the indices of invalid parentheses, allowing us to easily calculate the length of valid substrings.
- By continuously calculating the length and updating the maximum length, we ensure finding the longest valid substring.

Algorithm Walkthrough

Consider the input ")()())":

Initialize stack with -1: stack = [-1]
Iterate through the string:
- At index 0: ')'
  - Pop from stack: stack = []
  - Stack is empty, push index 0 onto stack: stack = [0]
- At index 1: '('
  - Push index 1 onto stack: stack = [0, 1]
- At index 2: ')'
  - Pop from stack: stack = [0]
  - Calculate length: 2 - 0 = 2
- At index 3: '('
  - Push index 3 onto stack: stack = [0, 3]
- At index 4: ')'
  - Pop from stack: stack = [0]
  - Calculate length: 4 - 0 = 4
- At index 5: ')'
  - Pop from stack: stack = []
  - Stack is empty, push index 5 onto stack: stack = [5]
The longest valid parentheses substring is of length 4.

Code

class Solution:
    def longestValidParentheses(self,s: str) -> int:
        max_length, stack = 0, [-1]  # Initialize variables
        for i, char in enumerate(s):
            if char == '(':  # If opening bracket, add index to stack
                stack.append(i)
            else:
                stack.pop()  # Pop for closing bracket
                if not stack:  # If stack is empty, add current index
                    stack.append(i)
                else:
                    # Calculate the length using the current index and the top of the stack
                    max_length = max(max_length, i - stack[-1])
        return max_length

# Testing the function
print(Solution().longestValidParentheses("(())"))  # Output: 4
print(Solution().longestValidParentheses(")()())"))  # Output: 4
print(Solution().longestValidParentheses("(()"))  # Output: 2

Complexity Analysis

Time Complexity: O(n), where n is the length of the input string. The algorithm traverses the string once.
Space Complexity: O(n), where n is the length of the input string. In the worst case, the stack will store all characters of the string.

Serialize and Deserialize Binary Tree

Problem Statement

Given a binary tree, your task is to create two functions.

one for serializing the tree into a string format and another for deserializing the string back into the tree.

The serialized string should retain all the tree nodes and their connections, allowing for reconstruction without any loss of data.

Examples

Example 1:
- Input: [1,2,3,null,null,4,5]
- Expected Output: [1,2,3,null,null,4,5]
- Justification
  
  : The tree has the structure:
  1
  2
  3
  4
  5
  1
  / \
  2 3
  / \
  4 5
  When serialized and then deserialized, it should retain the exact same structure.
Example 2:
- Input: [1,null,2,3]
- Expected Output: [1,null,2,3]
- Justification
  
  : The tree has the structure:
  1
  2
  3
  4
  5
  1
  \
  2
  /
  3
  When serialized and then deserialized, it should retain the exact same structure.
Example 3:
- Input: [5,4,7,3,null,null,null,2]
- Expected Output: [5,4,7,3,null,null,null,2]
- Justification
  
  : The tree has the structure:
  1
  2
  3
  4
  5
  6
  7
  5
  / \
  4 7
  /
  3
  /
  2

Constraints:

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

Solution

To serialize a binary tree, we will traverse it in a pre-order fashion (root-left-right) and generate a string representation. When we encounter a null value, we’ll represent it with a special character, say “X”. The serialized string will have each value separated by a comma.

For deserialization, we will split the string on commas and use a queue to help in the reconstruction. We’ll take the front of the queue and check if it’s “X”. If it is, then it’s a null node, otherwise, we create a new node with the value. The same approach applies recursively for the left and right children.

Serialization:
- Start from the root.
- If the current node is null, append “X,” to the result string.
- If not null, append its value and a comma to the result string.
- Recursively serialize the left subtree.
- Recursively serialize the right subtree.
Deserialization:
- Split the string by comma to get a list of nodes.
- Use a queue to facilitate tree reconstruction.
- For each value in the list:
  - If it’s “X”, return null.
  - Otherwise, create a new node.
  - Recursively deserialize the left and right children.

Algorithm Walkthrough:

Given the input: [1,2,3,null,null,4,5].

Serialization:
- Start with root: 1. Add “1,” to the result string.
- Go left: 2. Add “2,” to the result string.
- Go left: null. Add “X,” to the result string.
- Go back and go right: null. Add “X,” to the result string.
- Go back to 1 and go right: 3. Add “3,” to the result string.
- Go left: 4. Add “4,” to the result string.
- Left and right of 4 are null. Add “X,X,” to the result string.
- Go back to 3 and go right: 5. Add “5,” to the result string.
- Left and right of 5 are null. Add “X,X,” to the result string.
- Resulting serialized string: “1,2,X,X,3,4,X,X,5,X,X,”.
Deserialization:
- Split string by comma: [“1”,”2”,”X”,”X”,”3”,”4”,”X”,”X”,”5”,”X”,”X”].
- Start with “1”. Create a node with value 1.
- Move to next value “2”. Create a left child with value 2.
- Next is “X”. So, the left of 2 is null.
- Move to the next “X”. Right of 2 is also null.
- Next is “3”. Create a right child for root with value 3.
- Next is “4”. Create a left child for 3 with value 4.
- Two X’s indicate the left and right children of 4 are null.
- “5” is the right child of 3.
- Two X’s indicate the children of 5 are null.

Code

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def serialize(self, root: TreeNode) -> str:
        # Helper function to recursively serialize tree nodes.
        def helper(node):
            if not node:
                return "X,"
            left_serialized = helper(node.left)
            right_serialized = helper(node.right)
            return str(node.val) + "," + left_serialized + right_serialized
        return helper(root)
    
    def deserialize(self, data: str) -> TreeNode:
        # Convert string to a list for easy access and management.
        nodes = iter(data.split(","))
        
        # Helper function to recursively deserialize tree nodes.
        def helper():
            val = next(nodes)
            if val == "X":
                return None
            node = TreeNode(int(val))
            node.left = helper()
            node.right = helper()
            return node
        return helper()

# Main function to test the code
if __name__ == "__main__":
    solution = Solution()
    testTree = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
    serialized = solution.serialize(testTree)
    deserialized = solution.deserialize(serialized)
    print("Serialized:", serialized)
    print("Deserialized (Serialized again for verification):", solution.serialize(deserialized))

Complexity Analysis

Time Complexity

Serialization: We visit every node once and only once, which gives a time complexity of (O(n)), where (n) is the number of nodes in the tree.
Deserialization: Similarly, for deserialization, we reconstruct every node once and only once, so the time complexity is also (O(n)).

Space Complexity

Serialization: In the worst case, we have to append for every node and its two children. Additionally, there might be a considerable number of nulls (X), hence the space complexity would be (O(n)).
Deserialization: The primary space consumption lies in the recursion stack, which would be (O(h)), where (h) is the height of the tree. In the worst case, the tree could be skewed, making its height (n), so the space complexity would be (O(n)).

Author：Hasuer

Link：https://hasuer.github.io/33-test-your-knowledge-hard/index.html

Publish date：June 2nd 2024, 11:09:09 am

Update date：May 28th 2024, 11:32:34 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

Next Post

34. Conclusions
Previous Post

32. Test Your Knowledge (Medium)

CATALOG

1. Longest Valid Parentheses
2. Serialize and Deserialize Binary Tree