Minimum Flips to Separate X and Y
MediumUpdated: Aug 10, 2025
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
Input: "xyxxxyxyy"
Output: 2
Explanation:
We can flip the 2nd character (y→x) and 6th character (x→y):
"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
Input: "xxxyyyy"
Output: 0
Explanation:
Already all x's come before all y's, no flips needed.
Example 3
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
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 (y→x) → "xxxy" (1 flip)
Option 4: Flip position 2 (x→y) → "xyyy" (1 flip)
Minimum is 1 flip.
Example 5
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
- Handle edge cases: empty string or single character
- Calculate the cost for making all characters 'x' (count of y's)
- Calculate the cost for making all characters 'y' (count of x's)
- 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
- Track the minimum cost across all possibilities
- Use prefix sums to efficiently calculate costs for each split
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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
- Define DP states:
dpX[i]: minimum cost to have all x's up to position idpY[i]: minimum cost to have all y's from some switch point to position i
- Initialize base cases for position 0
- 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
- The answer is the minimum of final states
- Optimize space by using variables instead of arrays
Code
C++
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);
}
};
Go
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
}
Java
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);
}
}
Python
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
- Try all possible split points from 0 to n (n+1 possibilities)
- 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
- Track minimum cost across all split points
- Handle edge cases of empty ranges
Code
Python
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