643 . 電皇的小寫英文字母

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

joycewang

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

71.4% (10/14)

Tags

apcsc apcsc-timecomplexity

Description

電皇思朋有很多奇怪的興趣，其中一個興趣就是喜歡出奇怪的練習題羞辱同學。

你已被電皇羞辱。現在給你一個小寫英文字母組成的字串 $S$，求最短的子字串包含所有小寫英文字母。

Input Format

輸入只有一行，為電皇給你的字串 $S$，其中保證 $S$ 只由小寫英文字母 a 到 z 組成，且 $S$ 的長度不超過 $10^ 6$。

Output Format

輸出一行，為包含所有的小寫字母中最短的子字串。如果有多個最短的子字串，請輸出第一次出現的。如果這種子字串不存在，請輸出 QQ。

Sample Input 1

qwertyuiopasdfghjklzxcvbnm

Sample Output 1

qwertyuiopasdfghjklzxcvbnm

Sample Input 2

qaqaqwertyuiopasdfghjklzxcvbnpekopekopekomahoyahoyahoy

Sample Output 2

qwertyuiopasdfghjklzxcvbnpekopekopekom

Sample Input 3

roadorollada

Sample Output 3

QQ

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~21 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
Submit
Back to Top