Bedao Regular Contest 11 - ABSTRING

View as PDF

Submit solution


Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hương hoa bay nhẹ nhàng qua kẽ lá.

Lời thì thầm của đá khẽ qua tai.

Không cần giới thiệu chắc hẳn bạn cũng không biết 2 câu thơ trên là của ai. Nhưng theo mình biết, thì 2 câu thơ đó chính là châm ngôn sống của Lành - 1 người đàn ông mạnh mẽ nhưng sống rất nội tâm. Hằng ngày khi không có việc gì làm, Lành thường có những biểu hiện như tay nhặt lá, chân đá ống bơ (đúng như châm ngôn sống của mình). Những lúc khác thì Lành lại tự nghĩ ra những câu đố hóc búa, thách thức chính bản thân mình cũng như mọi người. Hôm nay cũng như vậy, Lành đã nghĩ ra bài toán như sau:

  • Cho một xâu kí tự chỉ chứa ~2~ kí tự '~a~' và '~b~', hãy ~1~ tìm xâu con liên tiếp sao cho tần suất xuất hiện là lớn nhất.
  • Tần suất xuất hiện là số lần xâu con liên tiếp '~aba~' xuất hiện / độ dài.

Tuy nhiên các xâu kí tự thì có vẻ rất dài, vì vậy các bạn lập trình viên của ~Bedao \ Contest~ hãy giúp đỡ Lành nhé.

Input

  • Dòng đầu tiên nhập số nguyên dương ~n \ (3 \le n \le 10^6)~ là độ dài của xâu kí tự.
  • Dòng thứ 2 nhập xâu kí tự có độ dài ~n~ chỉ chứa ~2~ kí tự '~a~' và '~b~' (Dữ liệu đảm bảo có ít nhất 1 xâu '~aba~').

Output

  • In ra 1 dòng duy nhất chứa xâu kí tự cần tìm. Nếu có nhiều xâu con có tần suất xuất hiện của xâu '~aba~' là lớn nhất thì in ra xâu có thứ tự từ điển nhỏ nhất.

Subtask

  • ~20\%~ số test có ~n \le 10^2~.
  • ~30\%~ số test có ~n \le 10^3~.
  • Còn lại không có điều kiện gì thêm.

Sample Input

8
abaababa

Sample Output

ababa   

Note

Ta thấy xâu '~ababa~' có tần suất xuất hiện là ~2/5~ là lớn nhất, còn xâu '~abaababa~' có tần suất xuất hiện là ~3/8~ bé hơn ~2/5~.


Comments

Please read the guidelines before commenting.



  • -6
    quoctuan   commented on Dec. 20, 2022, 9:30 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      clone_testcode   commented on Dec. 20, 2022, 8:16 p.m.

      Thiếu sự chú ý thì cũng đừng có xả rác lên đây. Bẩn lắm.