02/10/2018, 14:28

Complete The Word – Codeforces 716B (Div. 2)

1. Đề bài Codeforces 716B Đề bài cho bạn 1 xâu có độ dài <= 50000 kí tự, bao gồm ‘A’->’Z’ và dấu ‘?’. Người ta định nghĩa 1 xâu đẹp là xâu có 26 kí tự, các kí tự bao gồm ‘A’->’Z’ và mỗi chữ cái chỉ xuất ...

1. Đề bài Codeforces 716B

Đề bài cho bạn 1 xâu có độ dài <= 50000 kí tự, bao gồm ‘A’->’Z’ và dấu ‘?’. Người ta định nghĩa 1 xâu đẹp là xâu có 26 kí tự, các kí tự bao gồm ‘A’->’Z’ và mỗi chữ cái chỉ xuất hiện đúng 1 lần. Nhiệm vụ của bạn là tìm xem có cách nào điền chữ cái ‘A’->’Z’ vào dấu ? trong xâu ban đầu để xâu đó tồn tại một xâu con là xâu đẹp hay không?

Nếu có hãy in ra một xâu bất kì. nếu không tồn tại ghi ra -1.

Input

Gồm 1 dòng duy nhất là xâu ban đầu

Output

Ghi ra xâu con thỏa mãn hoặc -1 nếu ko tồn tại

Examples

input
output
input
output
input
output
input
output

2. Ý tưởng giải quyết

  • Đầu tiên bạn tạo mảng 1 chiều lưu lại số lần xuất hiện của kí tự trong xâu con a[0]->a[25]
  • sau đó bạn đếm xem có bao nhiêu chữ cái trong đó xuất hiện trên 1 lần. (đặt tên là biến dem)
  • sau đó bạn dựa vào dem để tính, và xác định xem đoạn con đó có khả năng là xâu con đẹp ko? nếu không thì bạn cứ tịnh tiến cái phạm vi thống kê số lần xuất hiện dần hết xâu a đồng thời cập nhật biến dem, nếu chỗ nào thỏa mãn (dem==0) thì bạn xử lí thôi.

Nhận xét: nếu độ dài xâu a < 26 -> không tồn tại

Độ phức tạp O(|s|)

3. Code Codeforces 716B

0