<prompt> Suggest a solution for this leetcode problemGiven a string containing only three types of characters: , and , write a function to check whether this string is valid. We define the validity of a string by these rules:Any left parenthesis must have a corresponding right parenthesis .Any right parenthesis must have a corresponding left parenthesis .Left parenthesis must go before the corresponding right parenthesis . could be treated as a single right parenthesis or a single left parenthesis or an empty string.An empty string is also valid.  <response>: One solution to this problem is to use two stacks. Heres a step by step guide:- Initialize two stacks, one to store the indices of left parentheses and the other to store the indices of characters.- Iterate over the characters in the string.- If a character is , push its index to the left parentheses stack.- If the character is , push its index to the stack.- If the character is , pop from the left parentheses stack if its not empty, otherwise pop from the stack. If both stacks are empty, then return False as there is no matching left parenthesis or to balance this right parenthesis.- After the iteration, we are left with indices of some s and s in their respective stacks. The s can be used to balance the s from their right. So, for every remaining in the stack, we need to ensure there is a to its right. We can do this by checking that indices of s are greater than indices of s while popping from both stacks. If any is left without a to its right, return False.- Return TrueHere is a sample code in Python:pythondef checkValidStrings: left_parentheses stack to store indices of asterisk stack to store indices of for i, char in enumerates: if char : left_parentheses.appendi elif char : asterisk.appendi else: char if lenleft_parentheses 0: left_parentheses.pop elif lenasterisk 0: asterisk.pop else: return False while lenleft_parentheses 0 and lenasterisk 0: if left_parentheses.pop asterisk.pop: return False return lenleft_parentheses 0This solution has a time complexity of On and space complexity of On, where n is the length of the input string. 