Python3 Program to Find Maximum number of 0s placed consecutively at the start and end in any rotation of a Binary String

In this problem, we need to find the maximum sum of consecutive zeros at the start and end of any rotation of a binary string. We can solve this using two approaches: generating all rotations or using an optimized observation-based method.

Problem Statement Find the total number of maximum consecutive zeros at the start and end of any rotation of the given binary string.

Examples

Example 1

binary_str = "00100100"
print(f"Input: {binary_str}")

Input: 00100100
Output: 4

Explanation Let's examine all rotations:

• 00100100 Starting zeros: 2, Ending zeros: 2, Sum: 4

• 01001000 Starting zeros: 0, Ending zeros: 3, Sum: 3

• 10010000 Starting zeros: 0, Ending zeros: 4, Sum: 4

• 00100001 Starting zeros: 2, Ending zeros: 0, Sum: 2

• 01000010 Starting zeros: 0, Ending zeros: 1, Sum: 1

• 10000100 Starting zeros: 0, Ending zeros: 2, Sum: 2

• 00001001 Starting zeros: 4, Ending zeros: 0, Sum: 4

• 00010010 Starting zeros: 3, Ending zeros: 1, Sum: 4

Example 2

# All zeros case
binary_str = "00000000"
print(f"Input: {binary_str}")
print("Output: 8 (string length)")

Input: 00000000
Output: 8 (string length)

Example 3

# All ones case
binary_str = "11111111"
print(f"Input: {binary_str}")
print("Output: 0 (no zeros)")

Input: 11111111
Output: 0 (no zeros)

Approach 1: Generate All Rotations

We concatenate the string with itself and extract substrings of original length to get all rotations. Then calculate the sum of starting and ending zeros for each rotation ?

def count_start_end_zeros_rotations(binary_str):
    n = len(binary_str)
    
    # Count total ones
    total_ones = binary_str.count('1')
    
    # If no ones, return string length
    if total_ones == 0:
        return n
    
    # Concatenate string with itself
    doubled_str = binary_str + binary_str
    max_zeros = 0
    
    # Check all rotations
    for i in range(n):
        rotation = doubled_str[i:i + n]
        
        # Count starting zeros
        start_zeros = 0
        for char in rotation:
            if char == '0':
                start_zeros += 1
            else:
                break
        
        # Count ending zeros
        end_zeros = 0
        for char in reversed(rotation):
            if char == '0':
                end_zeros += 1
            else:
                break
        
        # Update maximum
        total = start_zeros + end_zeros
        max_zeros = max(max_zeros, total)
    
    return max_zeros

# Test the function
test_string = "00100100"
result = count_start_end_zeros_rotations(test_string)
print(f"Maximum sum of start and end zeros: {result}")

Maximum sum of start and end zeros: 4

Time Complexity: O(N²) for generating and checking each rotation.
Space Complexity: O(N) for the concatenated string.

Approach 2: Optimized Solution

Based on observation, the answer is either the maximum consecutive zeros in the string or the sum of leading and trailing zeros in the original string ?

def count_start_end_zeros_optimized(binary_str):
    n = len(binary_str)
    
    # Count total ones
    total_ones = binary_str.count('1')
    
    # If no ones, return string length
    if total_ones == 0:
        return n
    
    # Find maximum consecutive zeros
    max_consecutive = 0
    current_consecutive = 0
    
    for char in binary_str:
        if char == '0':
            current_consecutive += 1
            max_consecutive = max(max_consecutive, current_consecutive)
        else:
            current_consecutive = 0
    
    # Count leading zeros
    leading_zeros = 0
    for char in binary_str:
        if char == '0':
            leading_zeros += 1
        else:
            break
    
    # Count trailing zeros
    trailing_zeros = 0
    for char in reversed(binary_str):
        if char == '0':
            trailing_zeros += 1
        else:
            break
    
    # Return maximum of consecutive zeros or sum of leading + trailing
    return max(max_consecutive, leading_zeros + trailing_zeros)

# Test the function
test_cases = ["00100100", "00000000", "11111111", "10000001"]

for test in test_cases:
    result = count_start_end_zeros_optimized(test)
    print(f"String: {test}, Result: {result}")

String: 00100100, Result: 4
String: 00000000, Result: 8
String: 11111111, Result: 0
String: 10000001, Result: 5

Time Complexity: O(N) for single traversal.
Space Complexity: O(1) constant space.

Comparison

Conclusion

The optimized approach uses the key insight that the maximum sum occurs either with maximum consecutive zeros or combining leading and trailing zeros. This reduces time complexity from O(N²) to O(N) while using constant space.