Xâu đối xứng (HSG'20)
Xem PDF
Điểm:
900 (p)
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
Cho một xâu ký tự \(S\) chỉ gồm các chữ cái thường a..z. Xâu đối xứng là xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Ví dụ: \(madam\), \(ioi\) là các xâu đối xứng.
Yêu cầu: Với xâu ký tự \(S\) cho trước, hãy tính số ký tự bỏ đi ít nhất để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.
Ví dụ:
- Cho xâu
aammmdathì cần bỏ 2 ký tựavàmthì xâu còn lại làammdavà xếp lại thànhmadamlà xâu đối xứng. - Cho xâu
aaabbccthì không cần bỏ ký tự thì xâu đó xếp lại thànhbcaaacblà xâu đối xứng.
Input
- Một xâu ký tự \(S\) có \(n\) ký tự (\(n \le 10^5\)) chỉ gồm các ký tự chữ cái thường
a..z.
Output
- Một số nguyên là số lượng ký ít nhất cần bỏ để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.
Scoring
- Subtask \(1\): (\(30\%\) số điểm): chỉ chứa 2 ký tự
avàb. - Subtask \(2\): (\(30\%\) số điểm): chỉ chứa 3 loại ký tự bất kỳ.
- Subtask \(3\): (\(40\%\) số điểm): trường hợp còn lại.
Example
Test 1
Input
aammmdaOutput
2Test 2
Input
aaabbccOutput
0
Bình luận
Ban đầu tưởng S là chuỗi nhị phân thì xài XOR AC rồi
a = input()
a = list(map(str,a))
b = []
for i in a:
if i not in b:
b.append(i)
c = -1
d = 1
for j in b:
e = a.count(j)
if e % 2 == 0 and d != 1:
c += 1
d -= 1
elif e % 2 != 0:
c += 1
print(c)
có thằng chép code nè admin
em check code rồi y thệt không khác gì editorial chỉ khác thiếu #include và using và cách thôi
tên user account: trieuanhtri
mong admin xét xử
hai đấm mới ac
one hit
hiểu được cả một vấn đề ạ!
for ascii từ 97 đến 122
e kag
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
1 bình luận nữa