Hey everyone had this problem in an interview and can't seem to figure out the best way to do it. Any help would be much appreciated.

Problem:

You are given a string S. Each character of the string is either 'W' or 'R'.

• W represents a white-colored flower.
• R represents a red-colored flower

A string is considered beautiful if all the white-colored flowers are on the left of all the red-colored flowers. You can replace any white-colored flower with a red-colored flower and vice versa.

Your task is to find the minimum number of replacements that must be made to make string S beautiful.

sample cases:

1.) input: "RWRW"

output: 2 ("WWRR" or "WWWW" or “RRRR”)

2.) input: "RRRR"

output: 0 ("RRRR")

3.) input: "RWWWRR"

output: 1 ("WWWWRR")

CodePudding user response：

This looks like a dynamic programming problem. Let

dp[i][0] = minimum number of changes if the i-th flower is white
dp[i][1] = minimum number of changes if the i-th flower is white

Base state:

dp[0][0] = int(arr[0] != “W”)
dp[0][1] = int(arr[0] != “R”)

Now, to calculate the values for dp[i], we look at the cases:

1. If arr[i] == “R”

• If arr[i-1] == “R”, then arr[i] has to be “R”.
• If arr[i-1] == “W”, then arr[i] can be “R” or “W”.
• arr[i][1] = min(arr[i-1][0], arr[i-1][1])
• arr[i][0] = arr[i-1][0] 1

2. If arr[i] == “W”

• If arr[i-1] == “R”, then arr[i] has to be “R” (so we’ll have to modify current flower).
• If arr[i-1] == “W”, then arr[i] can be “R” (which needs modification) or “W” (no modification needed).
• arr[i][0] = arr[i-1][0]
• arr[i][1] = min(arr[i-1][0], arr[i-1][1]) 1

In the end, your answer becomes min(dp[n-1][0], dp[n-1][1])

Simple Python implementation:

s = "RWWWRR"
n = len(s)
dp = [[0,0] for i in range(n)]
dp[0][0] = int(s[0] != "W")
dp[0][1] = int(s[0] != "R")
for i in range(1,n):
    if s[i] == "R":
        dp[i][1] = min(dp[i-1])
        dp[i][0] = dp[i-1][0]   1 
    else:
        dp[i][1] = min(dp[i-1])   1 
        dp[i][0] = dp[i-1][0]
    
print(min(dp[n-1]))

CodePudding user response：

This can be solved in a single pass through the array keeping O(1) state.

We do this by finding the best place to split the array so that in the solution all the flowers to the left are white and all the flowers to the right are red. That's the same as finding i from 0 to N that minimizes the number of red flowers to the left of i plus the number of white flowers to the right of i, because that's the numbers of flowers we'd have to change to split the array at i.

Suppose the length of the array is N, there's R total red flowers (so N-R red flowers), and let r[i] be the number of red flowers to the left of i, r'[i] the number of red flowers to the right of i, and the same for white flowers with w[i] and w'[i].

We want to find i such that r[i] w'[i] is minimized (the number of red flowers to the left of i plus the number of white flowers to the right of i -- these are the ones we'd have to change). But w'[i] w[i] = (N-R), and r[i] w[i] = i, so r[i] w'[i] = r[i] (N-i)-(R-r[i]) = 2r[i] - i (N - R).

Thus we need to find i that minimizes 2r[i] - i (N - R). Since N-R is constant, that's the same as finding i such that 2r[i] - i is minimized. By the time we've processed the whole array, we have the value for R, and can construct the return value.

Here's some python code that uses this method, along with some test cases.

def min_changes(A):
    best, besti = 1e12, -1
    r = 0
    for i in range(len(A) 1):
        v = 2 * r - i
        if v < best:
            besti, best = i, v
        if i < len(A):
            r  = A[i] == 'R'
    return best   len(A) - r, 'W' * besti   'R' * (len(A) - besti)

tests = [("RWRW", 2, "RRRR"), ("RRRR", 0, "RRRR"), ("RWWWRR", 1, "WWWWRR")]
for s, n, r in tests:
    gotn, gotr = min_changes(s)
    if gotn != n or gotr != r:
        print("FAILED",)
    print(s, gotn, gotr)