Chương trình tìm chuỗi nhỏ nhất theo từ điển sau một lần hoán đổi trong Python

Cho chuỗi s, tìm chuỗi nhỏ nhất theo thứ tự từ điển có thể đạt được bằng tối đa một lần hoán đổi hai ký tự.

Ví dụ

Đầu vào: "zyzx".
Đầu ra: "xyzz".

Thuật toán

1. Tạo mảng temp lưu chỉ mục ký tự nhỏ nhất từ phải sang trái.
2. Duyệt từ phải sang trái, cập nhật m (chỉ mục ký tự nhỏ nhất hiện tại).
3. Duyệt từ trái sang phải, tìm vị trí đầu tiên mà s[temp[i]] != s[i], hoán đổi và trả về kết quả.
4. Nếu không tìm thấy, trả về s gốc.

Mã nguồn Python

class Solution:
    def solve(self, s):
        temp = [0] * len(s)
        m = len(s) - 1
        for i in range(len(s)-1, -1, -1):
            if s[i] < s[m]:
                m = i
            temp[i] = m
        for i in range(len(s)):
            a = temp[i]
            if s[a] != s[i]:
                return s[:i] + s[a] + s[i+1:a] + s[i] + s[a+1:]
        return s

ob = Solution()
print(ob.solve("zyzx"))

Đầu vào / Đầu ra

Input: zyzx
Output: xyzz