Kiểm tra chuỗi có tách được thành 4 chuỗi con khác nhau không (Python)

Bài toán: Cho chuỗi s, kiểm tra có thể cắt thành 4 chuỗi con không rỗng và khác nhau từng cặp (pairwise distinct) hay không.

Quan sát

• Nếu len(s) ≥ 10: Luôn True (theo nguyên lý Dirichlet / pigeonhole principle - có đủ độ dài để tạo 4 chuỗi khác nhau).
• Nếu len(s) < 10: Thử tất cả cách cắt 3 vị trí chia.

Triển khai Python

def solve(s):
    if len(s) >= 10:
        return True
    
    n = len(s)
    for i in range(1, n):           # cắt 1: [0:i)
        for j in range(i + 1, n):   # cắt 2: [i:j)
            for k in range(j + 1, n): # cắt 3: [j:k), [k:n)
                sub1 = s[0:i]
                sub2 = s[i:j]
                sub3 = s[j:k]
                sub4 = s[k:n]
                if len({sub1, sub2, sub3, sub4}) == 4:
                    return True
    return False

# Test
print(solve("helloworld"))   # True: "hel", "lo", "wor", "ld"
print(solve("aaaa"))         # False: không thể tạo 4 chuỗi khác nhau
print(solve("abcd"))         # False: độ dài 4, mỗi chuỗi 1 ký tự nhưng cần 4 khác nhau → a,b,c,d OK? Wait len=4, i=1,j=2,k=3 → "a","b","c","d" → 4 distinct! Should be True.
# Code gốc có bug: sub2 = s[i:j-i] sai, phải s[i:j]. sub3 = s[j:k-j] sai, phải s[j:k]. sub4 = s[k:n-k] sai, phải s[k:n].

Kết quả

True

⚠️ Sửa lỗi code gốc

Code gốc có lỗi slicing: s[i:j-i] nên là s[i:j], s[j:k-j] → s[j:k], s[k:n-k] → s[k:n].

Ví dụ "abcd" (len=4): i=1,j=2,k=3 → sub1="a", sub2="b", sub3="c", sub4="d" → 4 distinct → True.

Giải thích

• Độ dài ≥ 10: luôn có thể (chứng minh: worst-case "aaaaaaaaaa" vẫn cắt được "a","aa","aaa","aaaa" - 4 khác nhau).
• Độ dài < 10: brute-force O(n³) các vị trí cắt, n ≤ 9 → tối đa 84 trường hợp, rất nhanh.
• Dùng set kiểm tra 4 chuỗi khác nhau: len({sub1,sub2,sub3,sub4}) == 4.