Problem

You are given a string consisting of the letters x and y, such as xyxxxyxyy. In addition, you have an operation called flip, which changes a single x to y or vice versa.

Determine how many times you would need to apply this operation to ensure that all x’s come before all y’s. In the preceding example, it suffices to flip the second and sixth characters, so you should return 2.

Examples

Example 1

1
2
3
4
5
6
7
8
Input: "xyxxxyxyy"
Output: 2
Explanation: 
We can flip the 2nd character (yx) and 6th character (xy):
"xyxxxyxyy"  "xxxxxxyyy"
Original: x y x x x y x y y
Flipped:  x x x x x x y y y
Positions 1 and 6 are flipped, total = 2 flips.

Example 2

1
2
3
4
Input: "xxxyyyy"
Output: 0
Explanation: 
Already all x's come before all y's, no flips needed.

Example 3

1
2
3
4
5
6
7
Input: "yyyxxx"
Output: 3
Explanation:
We need to flip all y's to x's or all x's to y's.
Better to flip the 3 x's to y's: "yyyyyy"
Or flip the 3 y's to x's: "xxxxxx"
Both require 3 flips, minimum is 3.

Example 4

1
2
3
4
5
6
7
8
Input: "xyxy"
Output: 1
Explanation:
Option 1: Flip positions 1,3 (y's)  "xxxx" (2 flips)
Option 2: Flip positions 0,2 (x's)  "yyyy" (2 flips)  
Option 3: Flip position 1 (yx)  "xxxy" (1 flip)
Option 4: Flip position 2 (xy)  "xyyy" (1 flip)
Minimum is 1 flip.

Example 5

1
2
3
4
Input: "x"
Output: 0
Explanation:
Single character is already properly arranged.

Solution

Method 1 - Prefix Optimization with Dynamic Approach

Intuition

To have all x’s before all y’s, we need to find the optimal split point where everything to the left becomes x and everything to the right becomes y. For each possible split point, we count the cost (number of y’s on the left + number of x’s on the right) and take the minimum. We also consider the cases where all characters become x or all become y.

Approach

  1. Handle edge cases: empty string or single character
  2. Calculate the cost for making all characters ‘x’ (count of y’s)
  3. Calculate the cost for making all characters ‘y’ (count of x’s)
  4. For each possible split point i (0 to n):
    • Left part [0, i-1] should be all x’s: count y’s in this part
    • Right part [i, n-1] should be all y’s: count x’s in this part
    • Total cost = y’s on left + x’s on right
  5. Track the minimum cost across all possibilities
  6. Use prefix sums to efficiently calculate costs for each split

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minFlips(string s) {
        if (s.empty()) return 0;
        
        int n = s.length();
        int totalX = 0, totalY = 0;
        
        // Count total x's and y's
        for (char c : s) {
            if (c == 'x') totalX++;
            else totalY++;
        }
        
        // Case 1: All become x (flip all y's)
        int minCost = totalY;
        
        // Case 2: All become y (flip all x's)
        minCost = min(minCost, totalX);
        
        // Case 3: Find optimal split point
        int leftY = 0;  // y's in left part
        
        for (int i = 0; i <= n; i++) {
            // Cost: leftY + rightX
            int rightX = totalX - (i - leftY);  // x's in right part
            minCost = min(minCost, leftY + rightX);
            
            // Update for next iteration
            if (i < n && s[i] == 'y') {
                leftY++;
            }
        }
        
        return minCost;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func minFlips(s string) int {
    if len(s) == 0 {
        return 0
    }
    
    n := len(s)
    totalX, totalY := 0, 0
    
    // Count total x's and y's
    for _, c := range s {
        if c == 'x' {
            totalX++
        } else {
            totalY++
        }
    }
    
    // Case 1: All become x (flip all y's)
    minCost := totalY
    
    // Case 2: All become y (flip all x's)
    if totalX < minCost {
        minCost = totalX
    }
    
    // Case 3: Find optimal split point
    leftY := 0 // y's in left part
    
    for i := 0; i <= n; i++ {
        // Cost: leftY + rightX
        rightX := totalX - (i - leftY) // x's in right part
        if leftY + rightX < minCost {
            minCost = leftY + rightX
        }
        
        // Update for next iteration
        if i < n && s[i] == 'y' {
            leftY++
        }
    }
    
    return minCost
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int minFlips(String s) {
        if (s.isEmpty()) return 0;
        
        int n = s.length();
        int totalX = 0, totalY = 0;
        
        // Count total x's and y's
        for (char c : s.toCharArray()) {
            if (c == 'x') totalX++;
            else totalY++;
        }
        
        // Case 1: All become x (flip all y's)
        int minCost = totalY;
        
        // Case 2: All become y (flip all x's)
        minCost = Math.min(minCost, totalX);
        
        // Case 3: Find optimal split point
        int leftY = 0;  // y's in left part
        
        for (int i = 0; i <= n; i++) {
            // Cost: leftY + rightX
            int rightX = totalX - (i - leftY);  // x's in right part
            minCost = Math.min(minCost, leftY + rightX);
            
            // Update for next iteration
            if (i < n && s.charAt(i) == 'y') {
                leftY++;
            }
        }
        
        return minCost;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def min_flips(self, s: str) -> int:
        if not s:
            return 0
        
        n = len(s)
        total_x = s.count('x')
        total_y = s.count('y')
        
        # Case 1: All become x (flip all y's)
        min_cost = total_y
        
        # Case 2: All become y (flip all x's)
        min_cost = min(min_cost, total_x)
        
        # Case 3: Find optimal split point
        left_y = 0  # y's in left part
        
        for i in range(n + 1):
            # Cost: left_y + right_x
            right_x = total_x - (i - left_y)  # x's in right part
            min_cost = min(min_cost, left_y + right_x)
            
            # Update for next iteration
            if i < n and s[i] == 'y':
                left_y += 1
        
        return min_cost

Complexity

  • ⏰ Time complexity: O(N), where N is the length of the string. We make two passes through the string
  • 🧺 Space complexity: O(1), only using constant extra space for counters

Method 2 - Dynamic Programming with State Tracking

Intuition

We can use dynamic programming where we track the minimum cost to reach each possible state at position i. The states are: continuing to place x’s, or having switched to placing y’s. This approach naturally handles the transition point optimization.

Approach

  1. Define DP states:
    • dpX[i]: minimum cost to have all x’s up to position i
    • dpY[i]: minimum cost to have all y’s from some switch point to position i
  2. Initialize base cases for position 0
  3. For each position, calculate transitions:
    • Continue with x’s: cost to flip current char to x if needed
    • Switch to y’s: take minimum of previous x states + cost to flip current char to y
  4. The answer is the minimum of final states
  5. Optimize space by using variables instead of arrays

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minFlipsDP(string s) {
        if (s.empty()) return 0;
        
        int n = s.length();
        
        // dpX: min cost if we're still in x region
        // dpY: min cost if we've switched to y region
        int dpX = (s[0] == 'x') ? 0 : 1;  // Cost to make first char x
        int dpY = (s[0] == 'y') ? 0 : 1;  // Cost to make first char y
        
        for (int i = 1; i < n; i++) {
            int newDpX = dpX + ((s[i] == 'x') ? 0 : 1);  // Continue x region
            int newDpY = min(dpX, dpY) + ((s[i] == 'y') ? 0 : 1);  // Switch or continue y region
            
            dpX = newDpX;
            dpY = newDpY;
        }
        
        return min(dpX, dpY);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func minFlipsDP(s string) int {
    if len(s) == 0 {
        return 0
    }
    
    n := len(s)
    
    // dpX: min cost if we're still in x region
    // dpY: min cost if we've switched to y region
    dpX := 0
    if s[0] != 'x' {
        dpX = 1
    }
    
    dpY := 0
    if s[0] != 'y' {
        dpY = 1
    }
    
    for i := 1; i < n; i++ {
        costX := 0
        if s[i] != 'x' {
            costX = 1
        }
        
        costY := 0
        if s[i] != 'y' {
            costY = 1
        }
        
        newDpX := dpX + costX  // Continue x region
        newDpY := min(dpX, dpY) + costY  // Switch or continue y region
        
        dpX = newDpX
        dpY = newDpY
    }
    
    return min(dpX, dpY)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int minFlipsDP(String s) {
        if (s.isEmpty()) return 0;
        
        int n = s.length();
        
        // dpX: min cost if we're still in x region
        // dpY: min cost if we've switched to y region
        int dpX = (s.charAt(0) == 'x') ? 0 : 1;  // Cost to make first char x
        int dpY = (s.charAt(0) == 'y') ? 0 : 1;  // Cost to make first char y
        
        for (int i = 1; i < n; i++) {
            int costX = (s.charAt(i) == 'x') ? 0 : 1;
            int costY = (s.charAt(i) == 'y') ? 0 : 1;
            
            int newDpX = dpX + costX;  // Continue x region
            int newDpY = Math.min(dpX, dpY) + costY;  // Switch or continue y region
            
            dpX = newDpX;
            dpY = newDpY;
        }
        
        return Math.min(dpX, dpY);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def min_flips_dp(self, s: str) -> int:
        if not s:
            return 0
        
        n = len(s)
        
        # dp_x: min cost if we're still in x region
        # dp_y: min cost if we've switched to y region
        dp_x = 0 if s[0] == 'x' else 1  # Cost to make first char x
        dp_y = 0 if s[0] == 'y' else 1  # Cost to make first char y
        
        for i in range(1, n):
            cost_x = 0 if s[i] == 'x' else 1
            cost_y = 0 if s[i] == 'y' else 1
            
            new_dp_x = dp_x + cost_x  # Continue x region
            new_dp_y = min(dp_x, dp_y) + cost_y  # Switch or continue y region
            
            dp_x = new_dp_x
            dp_y = new_dp_y
        
        return min(dp_x, dp_y)

Complexity

  • ⏰ Time complexity: O(N), where N is the length of the string. Single pass through the string
  • 🧺 Space complexity: O(1), only using constant space for DP variables

Method 3 - Brute Force Split Point Enumeration

Intuition

A straightforward approach is to explicitly try every possible split point and calculate the cost for each. Split at position i means positions [0, i-1] become x and positions [i, n-1] become y. We also consider the boundary cases of all x or all y.

Approach

  1. Try all possible split points from 0 to n (n+1 possibilities)
  2. For split at position i:
    • Count y’s in range [0, i-1] (these need to become x)
    • Count x’s in range [i, n-1] (these need to become y)
    • Total cost = count of y’s in left + count of x’s in right
  3. Track minimum cost across all split points
  4. Handle edge cases of empty ranges

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def min_flips_brute(self, s: str) -> int:
        if not s:
            return 0
        
        n = len(s)
        min_cost = float('inf')
        
        # Try every possible split point
        for split in range(n + 1):
            cost = 0
            
            # Left part [0, split-1] should be all x's
            for i in range(split):
                if s[i] == 'y':
                    cost += 1
            
            # Right part [split, n-1] should be all y's  
            for i in range(split, n):
                if s[i] == 'x':
                    cost += 1
            
            min_cost = min(min_cost, cost)
        
        return min_cost

Complexity

  • ⏰ Time complexity: O(N²), where N is the length of the string. For each of N+1 split points, we scan up to N characters
  • 🧺 Space complexity: O(1), only using constant extra space

Notes

  • Method 1 is the most efficient with optimal O(N) time complexity using prefix optimization
  • Method 2 provides an elegant DP solution that naturally handles state transitions
  • Method 3 offers a simple brute force approach for verification and understanding
  • The problem is essentially finding the optimal split point to minimize total flips
  • Edge cases include empty strings, single characters, and already sorted strings
  • The solution works by recognizing that the final arrangement must be xy (zero or more x’s followed by zero or more y’s)
  • Both Method 1 and 2 achieve linear time complexity and are suitable for large inputs