Scale Engineer

Minimum Suffix Flips

Med
#1409Time: 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.2 companies
Patterns
Greedy
Data structures
String
Companies
IBMJ.P. Morgan

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem