Description#
You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:
- Type-1: Remove the character at the start of the string
s and append it to the end of the string. - Type-2: Pick any character in
s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.
Return the minimum number of type-2 operations you need to perform such that s becomes alternating.
The string is called alternating if no two adjacent characters are equal.
- For example, the strings
"010" and "1010" are alternating, while the string "0100" is not.
Example 1:
Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".
Example 2:
Input: s = "010"
Output: 0
Explanation: The string is already alternating.
Example 3:
Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def minFlips(self, s: str) -> int:
n = len(s)
target = "01"
cnt = sum(c != target[i & 1] for i, c in enumerate(s))
ans = min(cnt, n - cnt)
for i in range(n):
cnt -= s[i] != target[i & 1]
cnt += s[i] != target[(i + n) & 1]
ans = min(ans, cnt, n - cnt)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int minFlips(String s) {
int n = s.length();
String target = "01";
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (s.charAt(i) != target.charAt(i & 1)) {
++cnt;
}
}
int ans = Math.min(cnt, n - cnt);
for (int i = 0; i < n; ++i) {
if (s.charAt(i) != target.charAt(i & 1)) {
--cnt;
}
if (s.charAt(i) != target.charAt((i + n) & 1)) {
++cnt;
}
ans = Math.min(ans, Math.min(cnt, n - cnt));
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int minFlips(string s) {
int n = s.size();
string target = "01";
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (s[i] != target[i & 1]) {
++cnt;
}
}
int ans = min(cnt, n - cnt);
for (int i = 0; i < n; ++i) {
if (s[i] != target[i & 1]) {
--cnt;
}
if (s[i] != target[(i + n) & 1]) {
++cnt;
}
ans = min({ans, cnt, n - cnt});
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func minFlips(s string) int {
n := len(s)
target := "01"
cnt := 0
for i := range s {
if s[i] != target[i&1] {
cnt++
}
}
ans := min(cnt, n-cnt)
for i := range s {
if s[i] != target[i&1] {
cnt--
}
if s[i] != target[(i+n)&1] {
cnt++
}
ans = min(ans, min(cnt, n-cnt))
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| function minFlips(s: string): number {
const n = s.length;
const target = '01';
let cnt = 0;
for (let i = 0; i < n; ++i) {
if (s[i] !== target[i & 1]) {
++cnt;
}
}
let ans = Math.min(cnt, n - cnt);
for (let i = 0; i < n; ++i) {
if (s[i] !== target[i & 1]) {
--cnt;
}
if (s[i] !== target[(i + n) & 1]) {
++cnt;
}
ans = Math.min(ans, cnt, n - cnt);
}
return ans;
}
|
