Bài toán: Cho chuỗi nhị phân s (độ dài ≥ 2). Kiểm tra có thể hoán vị các ký tự để được chuỗi xen kẽ 0101... hoặc 1010... không.
Điều kiện cần và đủ
- Độ dài chẵn: số 0 = số 1.
- Độ dài lẻ: |số 0 - số 1| = 1.
Vì chuỗi xen kẽ yêu cầu 0 và 1 luân phiên, chênh lệch tối đa 1.
Triển khai Python
def solve(s):
ones = s.count('1')
zeros = s.count('0')
if len(s) % 2 == 0:
return ones == zeros
return abs(ones - zeros) == 1
# Test
print(solve("1000111")) # True: 4 ones, 3 zeros, len=7 odd, diff=1 → "1010101"
print(solve("1100")) # True: 2 ones, 2 zeros, len=4 even → "1010" or "0101"
print(solve("111000")) # False: 3 ones, 3 zeros, len=6 even but can alternate? Wait 3=3, len=6 even → True? "101010" needs 3 ones 3 zeros. Yes True.
print(solve("111100")) # False: 4 ones, 2 zeros, len=6 even, not equal
Kết quả
True
Giải thích
- Đếm số 0 và 1 bằng
str.count(). - Kiểm tra điều kiện dựa trên chẵn/lẻ độ dài.
- Độ phức tạp: O(n) time, O(1) space.
- Lưu ý: chỉ kiểm tra khả thi, không xây dựng chuỗi kết quả.