Minimum Suffix Flips

MEDIUM

Description

You are given a 0-indexed binary string target of length n. You have another binary string s of length n that is initially set to all zeros. You want to make s equal to target.

In one operation, you can pick an index i where 0 <= i < n and flip all bits in the inclusive range [i, n - 1]. Flip means changing '0' to '1' and '1' to '0'.

Return the minimum number of operations needed to make s equal to target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initially, s = "00000".
Choose index i = 2: "00000" -> "00111"
Choose index i = 0: "00111" -> "11000"
Choose index i = 1: "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: Initially, s = "000".
Choose index i = 0: "000" -> "111"
Choose index i = 1: "111" -> "100"
Choose index i = 2: "100" -> "101"
We need at least 3 flip operations to form target.

Example 3:

Input: target = "00000"
Output: 0
Explanation: We do not need any operations since the initial s already equals target.

Constraints:

n == target.length
1 <= n <= 10⁵
target[i] is either '0' or '1'.

Approaches

Checkout 2 different approaches to solve Minimum Suffix Flips. Click on different approaches to view the approach and algorithm in detail.

Optimal Greedy Approach with State Tracking

A more efficient approach avoids the costly simulation of flips. We can observe that the decision to flip at index i only depends on the state of the string at i, which in turn is determined by the number of flips performed at indices before i. We can track this 'effective state' with a single variable as we iterate through the target string, making a greedy and optimal decision at each step.

Algorithm

Initialize flips = 0.
Initialize currentState = '0'.
Iterate through each character c of the target string.
If c is different from currentState:
- Increment flips.
- Update currentState by flipping it ('0' to '1' or '1' to '0').
Return flips.

We can process the string from left to right, maintaining the current effective state of the string s. Initially, s is all '0's, so the effective state is '0'.

Let's use a variable currentState to track this. currentState starts as '0'. For each character target[i], we compare it with currentState. If they are different, it means s[i] (after previous flips) is not what we want it to be. We must perform an operation at index i. This is the greedy choice, and it's optimal because any later flip won't affect s[i]. When we perform an operation, we increment our count and also flip our currentState variable, because this operation will invert the state for all subsequent characters.

Initialize flips = 0.
Initialize a character currentState = '0', representing the state of s due to flips so far.
Iterate through each character c of the target string from left to right.
If c is different from currentState:
- A flip is required. Increment flips.
- The flip operation inverts the state for all subsequent positions. Update currentState by flipping it.
After the loop, return flips.

class Solution {
    public int minFlips(String target) {
        int flips = 0;
        char currentState = '0';
        for (char c : target.toCharArray()) {
            if (c != currentState) {
                flips++;
                currentState = (currentState == '0') ? '1' : '0';
            }
        }
        return flips;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the target string. We iterate through the string only once.Space Complexity: O(1), as we only use a few variables to store the count and the current state, irrespective of the input size.

Pros and Cons

Pros:

Extremely efficient with O(n) time complexity.
Requires only O(1) constant extra space.
The greedy choice at each step is proven to be optimal.

Cons:

The logic is slightly more abstract than direct simulation and requires an insight into the state transitions.

Code Solutions

Checking out 3 solutions in different languages for Minimum Suffix Flips. Click on different languages to view the code.

class Solution {
public
  int minFlips(String target) {
    int ans = 0;
    for (int i = 0; i < target.length(); ++i) {
      int v = target.charAt(i) - '0';
      if (((ans & 1) ^ v) != 0) {
        ++ans;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Minimum Suffix Flips

Patterns:

Greedy

Data Structures:

String

Companies:

IBM |J.P. Morgan |