FilesExpand file tree

 master

/

MinimumAddToMakeParenthesesValid.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (48 loc) · 1.12 KB

 master

/

MinimumAddToMakeParenthesesValid.java

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (48 loc) · 1.12 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

/**

* 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

*/

class Solution {

public int minAddToMakeValid(String S) {

int left = 0;

int change = 0;

int index = 0;

while(index < S.length()) {

if (S.charAt(index) == '(') {

left++;

} else if (S.charAt(index) == ')') {

if (left > 0) {

left--;

} else if (left == 0) {

change++;

}

}

index++;

}

return change + left;

}

}