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.
Input: "xyxxxyxyy"Output: 2Explanation:
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.
Input: "yyyxxx"Output: 3Explanation:
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 is3.
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.
classSolution {
public:int minFlips(string s) {
if (s.empty()) return0;
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;
}
};
funcminFlips(sstring) int {
if len(s) ==0 {
return0 }
n:= len(s)
totalX, totalY:=0, 0// Count total x's and y'sfor_, c:=ranges {
ifc=='x' {
totalX++ } else {
totalY++ }
}
// Case 1: All become x (flip all y's)minCost:=totalY// Case 2: All become y (flip all x's)iftotalX < minCost {
minCost = totalX }
// Case 3: Find optimal split pointleftY:=0// y's in left partfori:=0; i<=n; i++ {
// Cost: leftY + rightXrightX:=totalX- (i-leftY) // x's in right partifleftY+rightX < minCost {
minCost = leftY+rightX }
// Update for next iterationifi < n&&s[i] =='y' {
leftY++ }
}
returnminCost}
classSolution {
publicintminFlips(String s) {
if (s.isEmpty()) return 0;
int n = s.length();
int totalX = 0, totalY = 0;
// Count total x's and y'sfor (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 pointint leftY = 0; // y's in left partfor (int i = 0; i <= n; i++) {
// Cost: leftY + rightXint rightX = totalX - (i - leftY); // x's in right part minCost = Math.min(minCost, leftY + rightX);
// Update for next iterationif (i < n && s.charAt(i) =='y') {
leftY++;
}
}
return minCost;
}
}
classSolution:
defmin_flips(self, s: str) -> int:
ifnot s:
return0 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 partfor 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 iterationif i < n and s[i] =='y':
left_y +=1return min_cost
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.
classSolution {
public:int minFlipsDP(string s) {
if (s.empty()) return0;
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;
}
returnmin(dpX, dpY);
}
};
classSolution {
publicintminFlipsDP(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 regionint dpX = (s.charAt(0) =='x') ? 0 : 1; // Cost to make first char xint dpY = (s.charAt(0) =='y') ? 0 : 1; // Cost to make first char yfor (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 regionint newDpY = Math.min(dpX, dpY) + costY; // Switch or continue y region dpX = newDpX;
dpY = newDpY;
}
return Math.min(dpX, dpY);
}
}
classSolution:
defmin_flips_dp(self, s: str) -> int:
ifnot s:
return0 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 =0if s[0] =='x'else1# Cost to make first char x dp_y =0if s[0] =='y'else1# Cost to make first char yfor i in range(1, n):
cost_x =0if s[i] =='x'else1 cost_y =0if s[i] =='y'else1 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)
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.
classSolution:
defmin_flips_brute(self, s: str) -> int:
ifnot s:
return0 n = len(s)
min_cost = float('inf')
# Try every possible split pointfor split in range(n +1):
cost =0# Left part [0, split-1] should be all x'sfor 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