Xâu đối xứng (HSG'20)

View as PDF

All submissions

Best submissions

Read editorial

Author:

Small

Problem type

Points: 900 (p) Time limit: 1.0s Memory limit: 640M Input: stdin Output: stdout

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 aammmda thì cần bỏ 2 ký tự a và m thì xâu còn lại là ammda và xếp lại thành madam là xâu đối xứng.
Cho xâu aaabbcc thì không cần bỏ ký tự thì xâu đó xếp lại thành bcaaacb là 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ự a và 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

aammmda

Output

Test 2

Input

aaabbcc

Output

Comments

-1

toilahoangmot24 3:14 p.m. 25 nov, 2024

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

1

hoangphucnguyen 4:13 p.m. 27 oct, 2024

Ban đầu tưởng S là chuỗi nhị phân thì xài XOR AC rồi

-1

foxdz 8:24 p.m. 4 oct, 2024

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)

-3

nguyenvanbinh280412 10:21 a.m. 2 aug, 2024 ← edited →

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ử

1 reply