-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinSwapBracketBalancing.java
More file actions
59 lines (52 loc) · 1.49 KB
/
MinSwapBracketBalancing.java
File metadata and controls
59 lines (52 loc) · 1.49 KB
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
50
51
52
53
54
55
56
57
58
59
package String;
import java.util.Stack;
public class MinSwapBracketBalancing {
public static int bracketBalance1(String s) {
int open[] = new int[s.length()];
int j =0;
for(int i=0;i<s.length();i++) if(s.charAt(i) == '[') open[j++] = i;
char ar[] = s.toCharArray();
int sum = 0, cnt =0, idx = 0;
for(int i=0;i<s.length();i++) {
if(ar[i] == '[') {
cnt++;
idx += 1;
}
else if(ar[i] == ']'){
cnt--;
}
if(cnt < 0) {
sum += open[idx] - i;
char t = ar[i];
ar[i] = ar[open[idx]];
ar[open[idx]] = t;
cnt = 1;
idx += 1;
}
}
return sum;
}
public static int bracketBalance2(String s) {
char ar[] = s.toCharArray();
int sum = 0, OCnt =0,CCnt = 0, mismatch = 0;
for(int i=0;i<s.length();i++) {
if(ar[i] == '[') {
OCnt++;
if(mismatch>0) {
sum = sum + mismatch;
mismatch--;
}
}
else if(ar[i] == ']'){
CCnt++;
mismatch = CCnt - OCnt;
}
}
return sum;
}
public static void main(String args[]) {
String s = "]][[";
System.out.println(bracketBalance2(s));
//System.out.println(bracketBalance1(s));
}
}