Welcome to Subscribe On Youtube
-
import java.util.Stack; /** Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid. Formally, a parentheses string is valid if and only if: It is the empty string, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string. Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid. Example 1: Input: "())" Output: 1 Example 2: Input: "(((" Output: 3 Example 3: Input: "()" Output: 0 Example 4: Input: "()))((" Output: 4 Note: S.length <= 1000 S only consists of '(' and ')' characters. */ public class Minimum_Add_to_Make_Parentheses_Valid { class Solution { public int minAddToMakeValid(String S) { int ans = 0, bal = 0; for (int i = 0; i < S.length(); ++i) { bal += S.charAt(i) == '(' ? 1 : -1; // It is guaranteed bal >= -1 if (bal == -1) { ans++; bal++; } } return ans + bal; } } class Solution2 { // I'm thinking using stack public int minAddToMakeValid(String S) { Stack<Character> sk = new Stack<>(); int count = 0; for (char each: S.toCharArray()) { if (each == '(') { sk.push(each); } else if (each == ')') { if (sk.isEmpty()) { // key is this case sk.push(each); } else if (sk.peek() == '(') { sk.pop(); } else { count += 1; } } } return count + sk.size(); } } } ############ class Solution { public int minAddToMakeValid(String s) { int ans = 0, cnt = 0; for (char c : s.toCharArray()) { if (c == '(') { ++cnt; } else if (cnt > 0) { --cnt; } else { ++ans; } } ans += cnt; return ans; } }
-
// OJ: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/ // Time: O(N) // Space: O(1) class Solution { public: int minAddToMakeValid(string s) { int left = 0, invalidRight = 0; for (char c : s) { if (c == '(') ++left; else if (left) --left; else ++invalidRight; } return invalidRight + left; } };
-
class Solution: def minAddToMakeValid(self, s: str) -> int: ans = cnt = 0 for c in s: if c == '(': cnt += 1 elif cnt: cnt -= 1 else: ans += 1 ans += cnt return ans ############ class Solution(object): def minAddToMakeValid(self, S): """ :type S: str :rtype: int """ if not S: return 0 stack = [] res = 0 for i, s in enumerate(S): if '(' == s: if stack and (stack[-1] == ')'): cnt = 0 while stack: if stack.pop() == ')': cnt -= 1 else: cnt += 1 if cnt == 0: break res += abs(cnt) stack.append('(') else: stack.append(')') cnt = 0 while stack: if stack.pop() == ')': cnt -= 1 else: cnt += 1 res += abs(cnt) return res
-
func minAddToMakeValid(s string) int { ans, cnt := 0, 0 for _, c := range s { if c == '(' { cnt++ } else if cnt > 0 { cnt-- } else { ans++ } } ans += cnt return ans }
-
class Solution { public int minAddToMakeValid(String S) { int addCount = 0; int curCount = 0; int length = S.length(); for (int i = 0; i < length; i++) { char c = S.charAt(i); if (c == '(') curCount++; else { if (curCount > 0) curCount--; else addCount++; } } addCount += curCount; return addCount; } } ############ class Solution { public int minAddToMakeValid(String s) { int ans = 0, cnt = 0; for (char c : s.toCharArray()) { if (c == '(') { ++cnt; } else if (cnt > 0) { --cnt; } else { ++ans; } } ans += cnt; return ans; } }
-
// OJ: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/ // Time: O(N) // Space: O(1) class Solution { public: int minAddToMakeValid(string s) { int left = 0, invalidRight = 0; for (char c : s) { if (c == '(') ++left; else if (left) --left; else ++invalidRight; } return invalidRight + left; } };
-
class Solution: def minAddToMakeValid(self, s: str) -> int: ans = cnt = 0 for c in s: if c == '(': cnt += 1 elif cnt: cnt -= 1 else: ans += 1 ans += cnt return ans ############ class Solution(object): def minAddToMakeValid(self, S): """ :type S: str :rtype: int """ if not S: return 0 stack = [] res = 0 for i, s in enumerate(S): if '(' == s: if stack and (stack[-1] == ')'): cnt = 0 while stack: if stack.pop() == ')': cnt -= 1 else: cnt += 1 if cnt == 0: break res += abs(cnt) stack.append('(') else: stack.append(')') cnt = 0 while stack: if stack.pop() == ')': cnt -= 1 else: cnt += 1 res += abs(cnt) return res
-
func minAddToMakeValid(s string) int { ans, cnt := 0, 0 for _, c := range s { if c == '(' { cnt++ } else if cnt > 0 { cnt-- } else { ans++ } } ans += cnt return ans }