# Minimum Suffix Flips
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-suffix-flips)
Canonical: https://scaleengineer.com/dsa/problems/minimum-suffix-flips
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
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 <= 105`
* `target[i]` is either `'0'` or `'1'`.

# Approaches
## Direct Simulation
This approach directly simulates the process described in the problem. We start with a string `s` of all zeros and iterate through the `target` string from left to right. At each position `i`, we check if the current character `s[i]` matches `target[i]`. If they don't match, it means we must perform a flip operation starting at index `i` to correct the character `s[i]`. We increment our operation count and then manually flip all characters in `s` from index `i` to the end of the string. We repeat this process until we have checked all positions up to `n-1`.
**Time:** O(n^2), where n is the length of the target string. The outer loop runs n times, and the inner loop for flipping the suffix can also run up to n times. · **Space:** O(n), as we use an auxiliary character array of size n to store the state of string `s`.
**Pros:** It is simple to understand and directly implements the logic from the problem description.
**Cons:** It is inefficient due to the nested loop structure, leading to a quadratic time complexity which is too slow for large inputs.
### Explanation
The algorithm works by maintaining an explicit representation of the string `s` and modifying it according to the rules. It's a straightforward translation of the problem statement into code.

*   Initialize a character array `s` of length `n` with all '0's.
*   Initialize an integer `operations` to 0.
*   Iterate with an index `i` from 0 to `n-1`.
*   Inside the loop, compare `s[i]` with `target.charAt(i)`.
*   If `s[i]` is not equal to `target.charAt(i)`:
    *   Increment `operations`.
    *   Perform a suffix flip on `s`: iterate with an index `j` from `i` to `n-1` and flip the character `s[j]` ('0' to '1', '1' to '0').
*   After the loop finishes, return `operations`.

```java
class Solution {
    public int minFlips(String target) {
        int n = target.length();
        char[] s = new char[n];
        for (int i = 0; i < n; i++) {
            s[i] = '0';
        }
        
        int operations = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] != target.charAt(i)) {
                operations++;
                for (int j = i; j < n; j++) {
                    s[j] = (s[j] == '0') ? '1' : '0';
                }
            }
        }
        return operations;
    }
}
```
### Algorithm
*   Initialize a character array `s` of length `n` with all '0's.
*   Initialize an integer `operations` to 0.
*   Iterate with an index `i` from 0 to `n-1`.
*   If `s[i]` is not equal to `target.charAt(i)`:
    *   Increment `operations`.
    *   Perform a suffix flip on `s` by iterating from `j = i` to `n-1` and flipping `s[j]`.
*   Return `operations`.

## 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.
**Time:** O(n), where n is the length of the target string. We iterate through the string only once. · **Space:** O(1), as we only use a few variables to store the count and the current state, irrespective of the input size.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minFlips(string target) {
    int ans = 0;
    for (char c : target) {
      int v = c - '0';
      if ((ans & 1) ^ v) {
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minFlips(self, target: str) -> int: ans = 0 for v in target: if (ans & 1) ^ int(v): ans += 1 return ans

```