Giả sử chúng ta có một chuỗi chữ thường s với các chữ cái x và y. Bây giờ hãy xem xét một phép toán trong đó chúng ta thay đổi một x thành y hoặc ngược lại. Chúng ta phải tìm số lần tối thiểu chúng ta cần thực hiện phép toán đó để đặt tất cả x đứng trước tất cả y.
Vì vậy, nếu đầu vào là s ="yxyyyyxyxx", thì đầu ra sẽ là 4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
y_left:=0
-
x_right:=number of "x" in s, res:=number of "x" in s
-
đối với mỗi mục trong s, thực hiện
-
nếu mục giống như "x", thì
-
x_right:=x_right - 1
-
-
nếu không,
-
y_left:=y_left + 1
-
-
res:=tối thiểu res và (y_left + x_right)
-
-
trả lại res
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution:
def solve(self, s):
y_left = 0
x_right = res = s.count("x")
for item in s:
if item == "x":
x_right -= 1
else:
y_left += 1
res = min(res, y_left + x_right)
return res
ob = Solution()
s = "yxyyyyxyxx"
print(ob.solve(s)) Đầu vào
"yxyyyyxyxx"
Đầu ra
4