Giả sử chúng ta có chuỗi chữ thường s, cần kiểm tra xem có thể biến s thành chuỗi hợp lệ bằng cách xóa tối đa 1 ký tự hay không. Chuỗi hợp lệ nghĩa là tất cả ký tự duy nhất trong chuỗi có tần suất xuất hiện giống nhau.
Ví dụ, s = "xyyzx", đầu ra True vì xóa 'z' được "xyyx" - tần suất x và y đều bằng 2.
Các bước giải quyết:
- size := 26 (số chữ cái).
- occurrence := mảng 26 phần tử lưu tần suất.
- occr1, occr1_cnt, occr2, occr2_cnt := 0.
- Tìm tần suất đầu tiên khác 0 gán cho occr1, occr1_cnt = 1.
- Tìm tần suất tiếp theo khác 0: nếu bằng occr1 thì tăng occr1_cnt, ngược lại gán cho occr2, occr2_cnt = 1.
- Duyệt các tần suất còn lại: cập nhật occr1_cnt, occr2_cnt; nếu gặp tần suất thứ 3 khác, trả về False.
- Nếu occr1_cnt > 1 và occr2_cnt > 1, trả về False.
- Trả về True.
Xem ví dụ dưới đây để hiểu rõ hơn:
Ví dụ
size = 26
def solve(s):
occurrence = [0] * size
for ch in s:
occurrence[ord(ch) - ord('a')] += 1
occr1 = occr1_cnt = 0
for i in range(size):
if occurrence[i] != 0:
occr1 = occurrence[i]
occr1_cnt = 1
break
occr2 = occr2_cnt = 0
for j in range(i + 1, size):
if occurrence[j] != 0:
if occurrence[j] == occr1:
occr1_cnt += 1
else:
occr2_cnt = 1
occr2 = occurrence[j]
break
for k in range(j + 1, size):
if occurrence[k] != 0:
if occurrence[k] == occr1:
occr1_cnt += 1
elif occurrence[k] == occr2:
occr2_cnt += 1
else:
return False
if occr1_cnt > 1 and occr2_cnt > 1:
return False
return True
s = "xyyzx"
print(solve(s))
Đầu vào
"xyyzx"
Đầu ra
True