Chương trình đếm số lần đảo ký tự để tất cả x đứng trước y trong Python

Cho chuỗi s chỉ chứa 'x' và 'y'. Mỗi phép toán đổi một 'x' thành 'y' hoặc ngược lại. Tìm số phép toán tối thiểu để tất cả 'x' đứng trước tất cả 'y'.

Ví dụ: s = "yxyyyyxyxx" → 4.

Giải pháp

Duyệt một lần, duy trì số 'y' bên trái (y_left) và số 'x' bên phải (x_right):

• Khởi tạo: y_left = 0, x_right = res = count('x')
• Duyệt từng ký tự:
  • Nếu 'x': x_right--
  • Nếu 'y': y_left++
  • res = min(res, y_left + x_right)
• res là số lần đổi tối thiểu (đổi y_left cái 'y' bên trái thành 'x' và x_right cái 'x' bên phải thành 'y')

Ví dụ minh họa

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