Xâu Đối Xứng

Nguồn: Bài tập trên trường (Câu 4) Độ khó: Dễ Xâu đối xứng Xử lý xâu Nhận xét

Đề bài

Câu 4: XÂU ĐỐI XỨNG

Cho trước một xâu $S$. Bạn hãy thay đổi đúng 1 kí tự, sao cho xâu mới thu được là một xâu đối xứng.

Input: Dòng đầu tiên là số lượng bộ test $T$ $(T \le 20)$. Mỗi test ghi trên một dòng 1 xâu $S$ có độ dài không quá 20 kí tự.

Output: Với mỗi test, in ra "YES" nếu có thể biến đổi xâu $S$ thành xâu đối xứng, in ra "NO" trong trường hợp ngược lại.

Ví dụ – input

3
abccaa
abbcca
abcda

Ví dụ – output

YES
NO
YES

Lời mở đầu

Bài này là bài tập trên trường của một bạn học viên nhắn tin hỏi mình. Bạn ấy ban đầu định "xoá các phần tử không lặp lại rồi kiểm tra xâu đối xứng", mình góp ý là hạn chế xoá/thêm, thật ra bài này chả cần thêm/xoá gì cả 😄. Mình với bạn ấy đã ngồi phân tích từng bước, giờ mình viết lại thành bài giải chi tiết để anh em cùng tham khảo nhé 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ cho bạn nào chưa hiểu đề. Một xâu đối xứng là xâu đọc xuôi hay đọc ngược đều giống nhau. Kiểm tra bằng cách đối chiếu từng cặp vị trí đầu – cuối rồi cứ thế đi vào giữa: cặp $(0, n-1)$, cặp $(1, n-2)$, ...

• abccaa: $s[0] = s[5]$ ✔, $s[1] \ne s[4]$ ✘ (b ≠ a), $s[2] = s[3]$ ✔ ⇒ chỉ lệch đúng 1 cặp. Sửa $s[1]$ thành a (hoặc $s[4]$ thành b) là được xâu đối xứng ⇒ YES.
• abbcca: $s[0] = s[5]$ ✔, $s[1] \ne s[4]$ ✘, $s[2] \ne s[3]$ ✘ ⇒ lệch tới 2 cặp, mà mỗi lần sửa 1 ký tự chỉ "chữa" được 1 cặp ⇒ NO.
• abcda: $s[0] = s[4]$ ✔, $s[1] \ne s[3]$ ✘, còn $s[2]$ là ký tự chính giữa ⇒ lệch 1 cặp ⇒ YES.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Thử đổi mọi ký tự · O(n²·C)Cách 2Đếm số cặp lệch · O(n)

Cách 1Làm đúng theo đề: thử đổi từng ký tự – O(n² · C)

Đề bảo "thay đổi đúng 1 kí tự" thì ta cứ làm y như vậy: thử mọi vị trí $i$, thử đổi $s[i]$ thành mọi ký tự $c$ khác $s[i]$ (ở đây mình thử hết các ký tự in được, mã ASCII từ 33 đến 126), mỗi lần đổi xong thì kiểm tra xâu mới có đối xứng không. Chỉ cần một lần thử thành công là in YES.

Với $|S| \le 20$ thì số lần thử chỉ cỡ $20 \cdot 94 \approx 1900$, mỗi lần kiểm tra mất $10$ phép so sánh ⇒ chạy tức thì. Cách này tuy "trâu" nhưng rất chắc, mình dùng nó làm code vét cạn để kiểm tra cách 2.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

bool doiXung(string s){
    int n = s.size();
    for(int i = 0; i < n / 2; i++)
        if(s[i] != s[n - i - 1]) return false;
    return true;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        string s;
        cin >> s;
        bool ok = false;
        // thử đổi ký tự ở vị trí i thành ký tự c (c phải khác s[i])
        for(int i = 0; i < (int)s.size() && !ok; i++){
            for(char c = 33; c <= 126 && !ok; c++){
                if(c == s[i]) continue;
                string t = s;
                t[i] = c;
                if(doiXung(t)) ok = true;
            }
        }
        if(ok) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

def doi_xung(s):
    return s == s[::-1]


T = int(input())
for _ in range(T):
    s = input().strip()
    ok = False
    # thử đổi ký tự ở vị trí i thành ký tự c (c phải khác s[i])
    for i in range(len(s)):
        for code in range(33, 127):
            c = chr(code)
            if c == s[i]:
                continue
            t = s[:i] + c + s[i + 1:]
            if doi_xung(t):
                ok = True
                break
        if ok:
            break
    print("YES" if ok else "NO")

Đánh giá độ phức tạp của cách làm này: có $n$ vị trí, mỗi vị trí thử $C = 94$ ký tự, mỗi lần kiểm tra đối xứng $O(n)$.

Không gian$O(n)$

Thời gian$O(n^2 \cdot C)$ mỗi test

Cách 2Đếm số cặp ký tự lệch nhau – O(n)

Đây là hướng mình đã phân tích cùng bạn học viên. Nhìn lại cách kiểm tra đối xứng: xâu đối xứng khi mọi cặp $(s[i], s[n-1-i])$ đều bằng nhau. Mỗi lần thay 1 ký tự thì chỉ tác động được tới đúng 1 cặp. Vậy gọi $dem$ là số cặp đang lệch nhau:

hiện tại s[0] với s[5] bằng nhau, s[1] với s[4] khác nhau, s[2] với s[3] bằng nhau

chỉ khác ở duy nhất 1 cặp là s[1] và s[4] ⇒ sửa lại s[1] = 'a' hoặc s[4] = 'b' là xâu đối xứng ⇒ YES

trong khi đó với ví dụ 2 (abbcca) cả thảy có đến 2 cặp khác nhau, chỉ cho sửa 1 cặp thì chắc ăn là không thoả rồi đó 🙂 – vậy đó là mấu chốt để giải bài này

Kết luận theo số cặp lệch dem

• $dem \ge 2$: sửa 1 ký tự không thể chữa hết ⇒ NO.
• $dem = 1$: sửa 1 ký tự của cặp lệch cho giống ký tự kia ⇒ YES.
• $dem = 0$ (xâu đã đối xứng sẵn): vẫn bắt buộc phải đổi đúng 1 ký tự! Nếu $n$ lẻ thì đổi ký tự chính giữa, xâu vẫn đối xứng ⇒ YES. Nếu $n$ chẵn thì đổi ký tự nào cũng làm lệch 1 cặp ⇒ NO.

Tối ưu nhỏ: dừng sớm

Hàm kiểm tra ban đầu của bạn học viên luôn chạy hết nửa xâu rồi mới trả về $dem$. Mình góp ý: chuỗi dài 1000 thì phải chạy 500 lần, trong khi giả sử mới 2 lần đầu đã thấy $dem \gt 1$ rồi thì đâu cần xét 498 lần còn lại ⇒ cứ dem > 1 là return false luôn.

Minh hoạ đối chiếu từng cặp

Em nhập một xâu rồi bấm Tiếp: mỗi bước so một cặp đầu – cuối (xanh = bằng nhau, đỏ = lệch), ô tím là ký tự chính giữa khi độ dài lẻ.

xâu S

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này (hàm Kiem_Tra giữ đúng như mình góp ý cho bạn học viên, có thêm nhánh $dem = 0$):

#include <bits/stdc++.h>
using namespace std;

bool Kiem_Tra(string s){
    int dem = 0;
    int n = s.size();
    for(int i = 0; i < n / 2; i++){
        if(s[i] != s[n - i - 1]){
            dem++;
            if(dem > 1) return false;
        }
    }
    if(dem == 1) return true;
    return n % 2 == 1;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        string s;
        cin >> s;
        if(Kiem_Tra(s)) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

def kiem_tra(s):
    dem = 0
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            dem += 1
            if dem > 1:
                return False
    if dem == 1:
        return True
    return n % 2 == 1   # dem == 0: chỉ đổi được ký tự chính giữa khi n lẻ


T = int(input())
for _ in range(T):
    s = input().strip()
    print("YES" if kiem_tra(s) else "NO")

C++▶ Chạy tay từng dòng codeCách 2: đếm số cặp lệch, dừng sớm khi dem > 1, xét riêng trường hợp xâu đã đối xứng.

Dữ liệu vào (stdin) – sửa thoải mái3 abccaa abbcca abcda

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4bool Kiem_Tra(string s){

5 int dem = 0;

6 int n = s.size();

7 for(int i = 0; i < n / 2; i++){

8 if(s[i] != s[n - i - 1]){

9 dem++;

10 if(dem > 1) return false;

11 }

12 }

13 if(dem == 1) return true;

14 return n % 2 == 1;

15}

16

17int main(){

18 int T;

19 cin >> T;

20 while(T--){

21 string s;

22 cin >> s;

23 if(Kiem_Tra(s)) cout << "YES\n";

24 else cout << "NO\n";

25 }

26 return 0;

27}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ lưu xâu $s$ ⇒ $O(n)$.
• Thời gian: mỗi xâu duyệt tối đa $n / 2$ cặp ⇒ $O(n)$ mỗi test, tổng $O(T \cdot n)$.

Không gian$O(n)$

Thời gian$O(n)$ mỗi test

Những chỗ dễ sai mà mình đã nhắc bạn học viên

• Đúng định dạng output: code ban đầu của bạn ấy in "\nYes", tức là thừa 1 dòng trống trước mỗi kết quả và viết sai chữ hoa/thường. Đề yêu cầu mỗi test in đúng 1 dòng YES hoặc NO, hệ thống chấm sẽ chấm sai ngay.
• Không cần ghi rõ điều kiện ở else: viết else if(kt >= 0 && kt < 2) là thừa, vì đã qua if(kt > 1) thì phần còn lại chắc chắn là $kt \le 1$. Chỉ cần else là được 😄.
• Đọc đủ T bộ test: đề có $T$ bộ test, nhớ đọc $T$ trước rồi lặp $T$ lần.
• Trường hợp xâu đã đối xứng sẵn: lúc trao đổi trong tin nhắn mình chỉ tập trung vào chuyện đếm cặp lệch nên hàm mẫu trả về true luôn khi $dem = 0$. Nhưng đề yêu cầu đổi đúng 1 ký tự, nên với xâu như abba (đối xứng, độ dài chẵn) đáp án phải là NO – đây cũng chính là nhận xét "số phần tử chẵn là NO còn lẻ là YES" mà bạn học viên nêu ra ngay từ đầu. Code trong bài đã bổ sung nhánh này.

Ghi chú của mình: code C++ và Python của cả 2 cách đã chạy đúng test đề, và được so khớp với nhau trên 300 bộ input ngẫu nhiên (mỗi bộ tới 20 xâu dài tới 20 ký tự, có nhiều xâu đối xứng sẵn hoặc chỉ lệch 1 ký tự) – kết quả giống hệt nhau.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇