-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFlip String to Monotone Increasing.kt
More file actions
50 lines (41 loc) · 1.38 KB
/
Flip String to Monotone Increasing.kt
File metadata and controls
50 lines (41 loc) · 1.38 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
class Solution {
fun minFlipsMonoIncr(s: String): Int {
val totalZeroFromRight = IntArray(s.length) { 0 }
val totalOneFromLeft = IntArray(s.length) { 0 }
var totalZero = 0
var totalOne = 0
for (i in 0 .. s.length - 1) {
if (s[i] == '1') {
totalOne++
}
// totalOne in currentIndex to left
totalOneFromLeft[i] = totalOne
}
for (i in (s.length - 1) downTo 0) {
if (s[i] == '0') {
totalZero++
}
// totalZero in currentIndex to right
totalZeroFromRight[i] = totalZero
}
var minFlip = Int.MAX_VALUE
var sum = 0
for (i in 0 .. s.length) {
if (i == 0) {
// total flip to change all into zero
sum = totalZeroFromRight[i]
} else if (i == s.length) {
// total flip to change all into one
sum = totalOneFromLeft[i-1]
} else {
// total flip to change all zero from right
// total flip to change all one from left
sum = totalZeroFromRight[i] + totalOneFromLeft[i-1]
}
minFlip = minOf(minFlip, sum)
}
return minFlip
}
}
// should not be '1' from the left of the last '0'
// should not be '0' from the right of the first '1'