You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.
The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.
Return the minimum number of operations needed to make s alternating.
Example 1:
Input: s = "0100" Output: 1 Explanation: If you change the last character to '1', s will be "0101", which is alternating.
Example 2:
Input: s = "10" Output: 0 Explanation: s is already alternating.
Example 3:
Input: s = "1111" Output: 2 Explanation: You need two operations to reach "0101" or "1010".
Constraints:
1 <= s.length <= 104s[i]is either'0'or'1'.
Solution: Two Counters
The final string is either 010101… or 101010…
We just need two counters to record the number of changes needed to transform the original string to those two final strings.
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int minOperations(string s) { int c1 = 0, c2 = 0; for (int i = 0; i < s.length(); ++i) { c1 += (s[i] - '0' == i % 2); c2 += (s[i] - '0' != i % 2); } return min(c1, c2); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment