1249. Minimum Remove to Make Valid ParenthesesGiven a string s of ‘(’ , ‘)’ and lowercase English characters.Your task is to remove the minimum number of parentheses ( ‘(’ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.Formally, a parentheses string is valid if and only if:It is the empty string, contains only lowercase characters, orIt can be written as AB (A concatenated with B), where A and B are valid strings, orIt can be written as (A), where A is a valid string.Example 1:Input:s “lee(t©o)de)”Output:“lee(t©o)de”Explanation:“lee(t(co)de)” , “lee(t©ode)” would also be accepted.Example 2:Input:s “a)b©d”Output:“ab©d”Example 3:Input:s “))((”Output:“”Explanation:An empty string is also valid.Constraints:1 s . l e n g t h 10 5 1 s.length 10^51s.length105s[i] is either ‘(’ , ‘)’, or lowercase English letter.From: LeetCodeLink: 1249. Minimum Remove to Make Valid ParenthesesSolution:Ideas:use a stack to match ‘(’. Mark unmatched ‘)’ and leftover ‘(’ for removal, then build the answer.Code:#includestdlib.h#includestring.h#includestdbool.hchar*minRemoveToMakeValid(char*s){intnstrlen(s);int*stack(int*)malloc(sizeof(int)*n);bool*remove(bool*)calloc(n,sizeof(bool));inttop0;for(inti0;in;i){if(s[i](){stack[top]i;}elseif(s[i])){if(top0){top--;}else{remove[i]true;}}}while(top0){remove[stack[--top]]true;}char*ans(char*)malloc(n1);intj0;for(inti0;in;i){if(!remove[i]){ans[j]s[i];}}ans[j]\0;free(stack);free(remove);returnans;}