1758. Minimum Changes To Make Alternating Binary String
Problem Description
You are given a binary string s that consists only of characters '0's and '1's. An operation is defined as changing a single character from '0' to '1' or from '1' to '0'. The goal is to transform the string into an alternating string, meaning no two adjacent characters will be the same. For instance, '010101' and '101010' are examples of valid alternating strings. You are asked to find the minimum number of operations required to achieve an alternating string from the given string s.
Intuition
To arrive at the least number of operations to make the string alternating, we can consider two cases:
- The string starts with '0': This means the string should follow the pattern '010101...'
- The string starts with '1': This would make the string follow '101010...'
For any given string s, these two cases are the only possible alternating strings that can be made without considering shifting the whole string.
Since we only need to consider the number of mismatches, we can iterate through the string once and count how many characters do not match the alternating pattern for each of the cases. The operation c != '01'[i & 1] checks if the character c at index i does not match the expected alternating character ('0' if i is even, '1' if odd). For each character, cnt is incremented if it mismatches.
Once the number of mismatches (cnt) for one pattern is determined, the minimum number of operations needed can either be cnt (changing all mismatched characters to match the pattern) or len(s) - cnt (changing all matched characters to flip the pattern). The minimum of these two values is the fewest number of operations needed to make the string s alternating, as changing all mismatched or all matched characters will achieve the same result.
Thus, our approach to solving the problem is to:
- Count the number of mismatches against one of the possible patterns.
- Calculate the operations needed to correct mismatches and to flip matches.
- Return the lower value between the two operations calculated.
Which algorithm should you use to find a node that is close to the root of the tree?
Solution Approach
The implementation provided in the reference solution applies a simple but efficient approach to solve the problem. It relies on string iteration, bitwise operations, and elementary arithmetic. No complex data structures are required. Here's a step-by-step breakdown of the approach used:
- The
enumeratefunction is used to iterate over the input strings, providing both the index (i) and the character (c) for each iteration. - For every character in the string, a check is performed using a bitwise AND operation
i & 1which efficiently determines the parity of the indexi(even or odd). Ifiis even,i & 1will be0; if odd, it will be1. - Based on the index parity, the character is compared against the expected character in an alternating string starting with '0' ('0' for even indices, '1' for odd indices). This is done using
'01'[i & 1], which indexes into the string'01'to pick the expected character. - The comparison
c != '01'[i & 1]results in a boolean value, which is then automatically cast to an integer (0forFalse,1forTrue) when used in arithmetic operations such as summation. - The
sumfunction totals the number of mismatchescntby counting every time the character does not meet the alternating condition based on its position (index parity). - Finally, the solution calculates the number of operations to transform the input string into an alternating string by taking the minimum between
cntandlen(s) - cnt. The latter represents the number of operations needed to achieve the opposite alternating pattern (starting with '1' instead of '0') which might require fewer operations.
The solution uses a common algorithmic pattern for problems of this nature: the greedy approach. It relies on the notion that a local optimal solution will lead to a globally optimal solution. In this case, addressing each character individually and deciding whether to flip it based on its position leads us to the minimum number of operations for the entire string.
Which of the following array represent a max heap?
Example Walkthrough
Let's consider a short example to illustrate the solution approach. Suppose we have the binary string s = "001".
Firstly, we'll consider the two patterns we can alternate from:
- Pattern starting with '0': "010"
- Pattern starting with '1': "101"
Now, we will calculate mismatches for the pattern starting with '0':
- For index 0: The given character is '0' and matches the expected '0', so the mismatch count (
cnt) remains 0. - For index 1: The given character is '0' but the expected character is '1'. This is a mismatch and
cntbecomes 1. - For index 2: The given character is '1' and matches the expected '1', so
cntremains 1.
Having finished the loop, we know that cnt for the pattern "010" is 1. This means we would need a minimum of 1 operation to turn "001" into "010".
However, we need to check against the opposite pattern too, starting with '1':
- For index 0: The given character is '0' but we expect '1'. This is a mismatch, so we start with
cnt1. - For index 1: The given character is '0' and since we're inverting our expectation, we want a '0' here. No mismatch,
cntremains 1. - For index 2: The given character is '1' and matches our expected '0' (since we invert at even indices). This is a mismatch, so
cntbecomes 2.
When we compare the number of operations needed, we have two possibilities:
- For the pattern starting with '0',
cntis 1. Therefore, we need 1 operation. - For the pattern starting with '1',
cntis 2. But instead of flipping mismatches, we can flip the rest and achieve the same pattern, which meanslen(s) - cnt = 3 - 2 = 1operation too.
Both patterns would require the same number of operations, just 1 in this case. The answer to the example would be that we need a single operation to make the string alternating. Thus, applying the logic from the solution approach, we take the minimum of cnt and len(s) - cnt, which is 1.
Solution Implementation
1class Solution:
2 def minOperations(self, string: str) -> int:
3 # Count the number of characters that do not match the pattern '01' repeated.
4 # '01'[i & 1] generates '0' for even i and '1' for odd i, which is the expected pattern.
5 mismatch_count = sum(char != '01'[index % 2] for index, char in enumerate(string))
6
7 # Since there are only two possible patterns ('01' repeated or '10' repeated),
8 # if mismatch_count is the cost of converting to pattern '01',
9 # then len(string) - mismatch_count will be the cost of converting to pattern '10'.
10 # We choose the minimum of these two costs as our result.
11 return min(mismatch_count, len(string) - mismatch_count)
121class Solution {
2 public int minOperations(String s) {
3 // 'count' variable counts how many operations are needed to make the string alternating (starting with '0')
4 int count = 0;
5 // The 'length' of the string
6 int length = s.length();
7
8 // Loop through each character in the string
9 for (int i = 0; i < length; ++i) {
10 // Check if the current character does not match the pattern '01' alternately
11 // by checking the parity of the index i (even or odd) using bitwise AND with 1 (i & 1)
12 if (s.charAt(i) != "01".charAt(i & 1)) {
13 // If it does not match, increment the 'count' (operation needed)
14 count += 1;
15 }
16 // Note: No need to do anything if it matches since no operation is needed
17 }
18
19 // The minimum operations would be the smaller of 'count' or the inverse operations needed (length - count)
20 // This is to account for the possibility that starting with '1' might require fewer operations
21 return Math.min(count, length - count);
22 }
23}
241class Solution {
2public:
3 // Function to return the minimum number of operations required
4 // to make all the characters at odd indices equal to '0' and
5 // even indices equal to '1' or vice versa in the given string 's'.
6 int minOperations(string s) {
7 int count = 0; // Initialize count of operations.
8 int length = s.size(); // Get the size of the string.
9
10 // Iterate over the string characters.
11 for (int i = 0; i < length; ++i) {
12 // Check if the current character does not match the expected pattern.
13 // The pattern is '01' for even indices and '10' for odd indices.
14 // The expression "01"[i & 1] effectively toggles between '0' and '1'.
15 count += s[i] != "01"[i & 1];
16 }
17
18 // Return the minimum of the count of changes if we start with '0'
19 // and the count if we start with '1'. The latter is given by (length - count)
20 // since it represents the number of positions that match the pattern when starting with '0'
21 // and therefore do not match the pattern when starting with '1'.
22 return std::min(count, length - count);
23 }
24};
251/**
2 * Computes the minimum number of operations to make a binary string alternate
3 * between '0' and '1' characters.
4 * @param {string} binString - The input binary string to transform.
5 * @return {number} The minimum number of operations required.
6 */
7function minOperations(binString: string): number {
8 // n stores the length of the input binary string.
9 const n: number = binString.length;
10 // count will hold the number of changes needed to match '01' alternating pattern.
11 let changeCount: number = 0;
12
13 // Iterate over each character in the binary string.
14 for (let i = 0; i < n; i++) {
15 // If the current character does not match the '01' pattern, increment changeCount.
16 // '01'[i & 1] will alternate between '0' for even i and '1' for odd i.
17 // The expression (i & 1) is equivalent to (i % 2), but may be more efficient.
18 if (binString[i] !== '01'[i & 1]) {
19 changeCount++;
20 }
21 }
22
23 // The result is the minimum between changeCount and the number of operations
24 // to match the opposite pattern (starting with '1'). This is because we can
25 // start with either '0' or '1', and we want the minimum of both options.
26 return Math.min(changeCount, n - changeCount);
27}
28Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Time and Space Complexity
The time complexity of the given code is O(n), where n is the length of the input string s. This is because there is a single loop in the code iterating through the string, and within the loop, basic operations are performed which take constant time.
The space complexity of the code is O(1). This is due to the use of a fixed amount of extra space, which is a few variables (cnt and computed values of len(s) - cnt), regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.