求O(|s|)时间复杂度的二进制字符串合规修改最小次数解法

Let's start by breaking down why your original approach fails for most test cases, then walk through two efficient O(n) solutions—including a super-simple linear scan that's easy to implement and understand.

What's Wrong With Your Current Code? #

Your algorithm has two critical flaws:

1. Overcounts modifications for short windows: When i is near the end of the string (so i + d > n), your code checks windows shorter than d—but the problem only requires validating substrings of length at least d. These short segments don't need changes, but your code incorrectly counts modifications for them.
2. Redundant and suboptimal traversal: When you find a '1' in a window, you increment i by 1 instead of jumping past the range this '1' covers. This leads to O(n²) time complexity and can miss optimal modification points (like placing a '1' as far right as possible to cover more ground).

For example, with "010000" and d=3, your code would incorrectly count 2 modifications instead of the optimal 1.

Key Insight: Rephrase the Problem #

The problem is equivalent to: eliminate all runs of d consecutive '0's with the minimum number of flips.

Why? If there’s a run of d '0's, that’s a substring of length d with no '1's (violating the condition). Conversely, if there are no such runs, every substring of length ≥d must contain at least one '1' (since a longer substring without any '1's would imply a run of ≥d '0's).

Solution 1: Simple Linear Scan (O(n) Time) #

This approach traverses the string once, tracking consecutive '0's. Whenever we hit d consecutive '0's, we flip the d-th '0' to '1' (incrementing our modification count) and reset the consecutive '0' counter (since this flip breaks the run).

public static int minimumMoves(String s, int d) {
    int n = s.length();
    if (n < d) return 0; // No substrings of length >=d exist
    
    int modifications = 0;
    int consecutiveZeros = 0;
    
    for (char c : s.toCharArray()) {
        if (c == '0') {
            consecutiveZeros++;
            // We've found a run of d zeros: flip the last one to 1
            if (consecutiveZeros == d) {
                modifications++;
                consecutiveZeros = 0; // Reset, since the flipped '1' breaks the run
            }
        } else {
            consecutiveZeros = 0; // Reset when we hit a '1'
        }
    }
    
    return modifications;
}

Solution 2: Greedy Placement (O(n) Time) #

If you want explicit control over where modifications are placed (e.g., choosing the rightmost position in each problematic window to maximize coverage), this greedy approach ensures each modification covers the largest possible range:

public static int minimumMoves(String s, int d) {
    int n = s.length();
    if (n < d) return 0;
    
    int modifications = 0;
    int i = 0;
    
    while (i <= n - d) {
        // Find the rightmost '1' in the current window [i, i+d-1]
        int rightmostOne = -1;
        for (int j = i; j < i + d; j++) {
            if (s.charAt(j) == '1') {
                rightmostOne = j;
            }
        }
        
        if (rightmostOne != -1) {
            // Jump past the start of the next possible problematic window
            i = rightmostOne + 1;
        } else {
            // No '1' in the window: flip the last character to '1'
            modifications++;
            // Jump past this window (the new '1' covers up to i+2d-1)
            i += d;
        }
    }
    
    return modifications;
}

Time Complexity #

Both solutions run in O(n) time:

• Solution 1: A single linear scan with no nested loops.
• Solution 2: Each character is checked at most once by the inner loop (since we jump i forward after processing each window, avoiding redundant checks).

Example Walkthrough (Solution 1) #

Take "010000" with d=3:

1. Position 0: '0' → consecutiveZeros = 1
2. Position 1: '1' → consecutiveZeros reset to 0
3. Position 2: '0' → consecutiveZeros = 1
4. Position 3: '0' → consecutiveZeros = 2
5. Position 4: '0' → consecutiveZeros hits 3 → increment modifications to 1, reset consecutiveZeros to 0
6. Position 5: '0' → consecutiveZeros = 1

Result: 1 modification (correct—flip position 4 to '1' to eliminate the run of 3 zeros).

内容的提问来源于stack exchange，提问作者Karthick Shiva