-
Notifications
You must be signed in to change notification settings - Fork 3
/
FlipStringToMonotoneIncreasing926.kt
68 lines (52 loc) · 1.28 KB
/
FlipStringToMonotoneIncreasing926.kt
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
60
61
62
63
64
65
66
67
68
package medium
/**
* A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).
You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.
Example 1:
Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.
Example 2:
Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.
Constraints:
1 <= s.length <= 105
s[i] is either '0' or '1'.
*/
fun minFlipsMonoIncr(s: String): Int {
var res = 0
var ones = 0
for (i in s.indices) {
if (s[i] == '0')
res++
else
ones++
res = Math.min(res, ones)
}
return res
}
fun minFlipsMonoIncrSol2(s: String): Int {
var zeroToOnes = 0
var onesCount = 0
var i = 0
while (i < s.length && s[i] == '0') {
i++
}
while (i < s.length) {
if (s[i] == '0') {
zeroToOnes++
} else {
onesCount++
}
if (zeroToOnes > onesCount)
zeroToOnes = onesCount
i++
}
return zeroToOnes
}