Leetcode 1869: Longer Contiguous Segments of Ones than Zeros
You are given a binary string s. Your task is to determine whether the longest contiguous segment of 1’s is strictly longer than the longest contiguous segment of 0’s. Return true if this condition holds, otherwise return false.
Problem
Approach
Steps
Complexity
Input: The input consists of a binary string s containing only '0' and '1'.
Example: "101100101"
Constraints:
• 1 <= s.length <= 100
• s[i] is either '0' or '1'
Output: Return true if the longest contiguous segment of 1's is strictly longer than the longest contiguous segment of 0's; otherwise return false.
Example: true
Constraints:
• The result is a boolean value (true or false).
Goal: To find the longest contiguous segments of 1's and 0's in the binary string and compare their lengths.
Steps:
• Iterate through the string to identify the lengths of contiguous segments of 1's and 0's.
• Track the maximum length of the 1's and 0's segments.
• Return true if the longest 1's segment is longer than the longest 0's segment; otherwise return false.
Goal: Constraints on the length of the string and its content.
Steps:
• 1 <= s.length <= 100
• s[i] is either '0' or '1'
Assumptions:
• The input string s is valid, containing only '0' or '1'.
• Input: "10101"
• Explanation: In this example, the longest contiguous segment of 1's is 2, and the longest contiguous segment of 0's is 1, so the answer is true.
Approach: The approach is to scan through the binary string, track the longest contiguous segments of 1's and 0's, and then compare their lengths.
Observations:
• We need to handle both the 1's and 0's segments efficiently.
• It would be efficient to iterate through the string once and calculate the maximum lengths of both 1's and 0's.
Steps:
• Initialize two counters for the lengths of 1's and 0's.
• Iterate through the string character by character, updating the counters for 1's and 0's.
• After each update, compare and store the maximum length found for 1's and 0's.
• At the end of the iteration, compare the longest segment of 1's with the longest segment of 0's and return the appropriate boolean result.
Empty Inputs:
• The string is never empty based on the given constraints.
Large Inputs:
• For large strings, the approach should still work in O(n) time complexity.
Special Values:
• When the string consists entirely of 0's or 1's, the answer should be determined based on the other segment's length being 0.
Constraints:
• Handle strings with a mix of 1's and 0's, as well as strings consisting of only 1's or only 0's.
bool checkZeroOnes(string s) {
int z = 0, o = 0, gz = 0, oz = 0, res = 1;
for(int i = 0; i < s.size(); i++) {
if(s[i] == '0') z++;
else z = 0;
if(s[i] == '1') o++;
else o = 0;
gz = max(gz, z);
oz = max(oz, o);
}
return oz > gz;
}
1 : Function Definition
bool checkZeroOnes(string s) {
Define the `checkZeroOnes` function, which accepts a string `s` representing a binary number and returns a boolean indicating whether the longest sequence of 1's is longer than the longest sequence of 0's.
2 : Variable Declaration
int z = 0, o = 0, gz = 0, oz = 0, res = 1;
Declare integer variables to track the number of consecutive 0's (`z`), 1's (`o`), and their respective maximum counts (`gz` for 0's and `oz` for 1's). A variable `res` is also initialized but not used in this implementation.
3 : Loop Initialization
for(int i = 0; i < s.size(); i++) {
Start a loop that iterates over each character in the input string `s`.
4 : Condition Check (Zero)
if(s[i] == '0') z++;
Check if the current character is '0'. If true, increment the count of consecutive 0's (`z`).
5 : Reset Zero Count
else z = 0;
If the current character is not '0', reset the count of consecutive 0's (`z`) to 0.
6 : Condition Check (One)
if(s[i] == '1') o++;
Check if the current character is '1'. If true, increment the count of consecutive 1's (`o`).
7 : Reset One Count
else o = 0;
If the current character is not '1', reset the count of consecutive 1's (`o`) to 0.
8 : Update Max Zero Count
gz = max(gz, z);
Update the maximum count of consecutive 0's (`gz`) to the greater of the current `gz` and the current count of consecutive 0's (`z`).
9 : Update Max One Count
oz = max(oz, o);
Update the maximum count of consecutive 1's (`oz`) to the greater of the current `oz` and the current count of consecutive 1's (`o`).
10 : Return Statement
return oz > gz;
Return a boolean indicating whether the longest sequence of 1's (`oz`) is greater than the longest sequence of 0's (`gz`).
Best Case: O(n) where n is the length of the string.
Average Case: O(n) for each scan through the string.
Worst Case: O(n) for a string of length n, as we must traverse the entire string.
Description: The time complexity is linear because we only iterate through the string once.
Best Case: O(1) for the same reason.
Worst Case: O(1) since we are using only a few variables to track the maximum segment lengths.
Description: The space complexity is constant because no additional data structures are needed.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus