Chương trình tìm chuỗi không phải palindrome nhỏ nhất theo thứ tự từ điển trong Python

Mô tả bài toán

Cho chuỗi s là palindrome. Thay đổi đúng một ký tự sao cho chuỗi không còn là palindrome và là nhỏ nhất theo thứ tự từ điển.

Ví dụ: s = "level" → đầu ra "aevel" (thay 'l' đầu tiên thành 'a').

Giải thuật (Tham lam)

1. Duyệt chỉ số i từ 0 đến len(s)//2 - 1:
   • Nếu s[i] != 'a': thay s[i] thành 'a', trả về chuỗi mới.
2. Nếu không tìm thấy (toàn 'a' ở nửa đầu): thay ký tự cuối thành 'b', trả về.

Ví dụ mã Python

class Solution:
    def solve(self, s):
        for i in range(len(s) // 2):
            if s[i] != "a":
                s = list(s)
                s[i] = "a"
                return "".join(s)
        s = list(s)
        s[-1] = "b"
        return "".join(s)

ob = Solution()
s = "level"
print(ob.solve(s))

Đầu vào

"level"

Đầu ra

aevel