Leetcode 2914: Minimum Number of Changes to Make Binary String Beautiful
You are given a 0-indexed binary string
s of even length. A string is considered beautiful if it can be divided into substrings where each substring has an even length and contains only ‘0’s or only ‘1’s. You can modify any character in s to ‘0’ or ‘1’. The task is to return the minimum number of changes required to make the string beautiful.Problem
Approach
Steps
Complexity
Input: You are given a binary string `s` with even length, where each character is either '0' or '1'.
Example: s = '1010'
Constraints:
• 2 <= s.length <= 10^5
• s has an even length
• s[i] is either '0' or '1'
Output: Return the minimum number of changes needed to make the string beautiful.
Example: For `s = '1010'`, the output is 2.
Constraints:
Goal: The goal is to transform the given string into a beautiful string by changing the minimum number of characters.
Steps:
• Iterate over the string in steps of 2.
• For each pair of adjacent characters, check if they are equal.
• If they are not equal, increment the change counter.
• Return the total number of changes.
Goal: The string length is guaranteed to be even. Each character of the string is either '0' or '1'.
Steps:
• The length of the string is between 2 and 100,000.
• The string has an even length.
Assumptions:
• The string length is always even.
• The string contains only '0' and '1'.
• Input: s = '1010'
• Explanation: The possible partition is: '10' | '10'. The string is not beautiful because the two substrings are not uniform. We need to change one '0' to '1' and one '1' to '0', resulting in the string '1111'. The minimum number of changes is 2.
• Input: s = '1100'
• Explanation: The string '1100' is already beautiful because it can be partitioned into '11' | '00'. No changes are needed.
Approach: We need to ensure that every pair of adjacent characters in the string is uniform (either both '0' or both '1'). If they are not, we increment the change counter. The problem requires checking pairs and determining the minimum number of changes.
Observations:
• The string must be modified to have consecutive pairs of equal characters.
• The solution requires iterating through the string and checking adjacent characters.
• By checking pairs in the string, we can directly calculate the number of required changes.
Steps:
• Start iterating through the string in steps of 2.
• For each consecutive pair, check if both characters are the same.
• If they are different, increment the change counter by 1.
• Return the total count of changes.
Empty Inputs:
• The input will never be empty since the string length is guaranteed to be even and at least 2.
Large Inputs:
• The solution needs to handle strings with a length of up to 100,000 efficiently.
Special Values:
• When the string consists entirely of '0's or '1's, no changes are needed.
Constraints:
• The string length will always be even.
• All characters in the string will be either '0' or '1'.
// time/space: O(n)/O(1)
int minChanges(string s) {
int result = 0;
int n = s.size();
for (int i = 0; i < n; i += 2) {
const char& a = s[i];
const char& b = s[i + 1];
if (a != b) result++;
}
return result;
}
1 : Function Definition
int minChanges(string s) {
Defines the function `minChanges` which takes a string `s` as input and returns the minimum number of changes required.
2 : Variable Initialization
int result = 0;
Initializes the variable `result` to 0. This will hold the count of changes needed.
3 : Variable Initialization
int n = s.size();
Initializes the variable `n` to store the size of the string `s`.
4 : Loop: Iterate Over String
for (int i = 0; i < n; i += 2) {
Starts a loop that iterates through the string `s`, incrementing `i` by 2 each time, so it checks every pair of adjacent characters.
5 : Variable Assignment
const char& a = s[i];
Assigns the character at index `i` of the string `s` to the reference variable `a`.
6 : Variable Assignment
const char& b = s[i + 1];
Assigns the character at index `i + 1` of the string `s` to the reference variable `b`.
7 : Conditional Check
if (a != b) result++;
Checks if the characters `a` and `b` are different. If they are, it increments the `result` variable by 1, indicating a change is needed.
8 : Return Statement
return result;
Returns the final value of `result`, which represents the minimum number of changes needed to make every pair of adjacent characters in the string the same.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we are iterating through the string with a step of 2, which is a linear operation.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since we are only using a constant amount of extra space to keep track of the change count.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus