QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#502564 | #3259. Substring Characters | yundaehyuck | AC ✓ | 57ms | 10880kb | Python3 | 1.2kb | 2024-08-03 09:43:29 | 2024-08-03 09:43:36 |
Judging History
answer
def generalized_period(s):
return set(s)
def minimal_proper_substrings(s, gen_period):
n = len(s)
minimal_substrings = set()
for i in range(n):
for j in range(i + 1, n + 1):
if j - i < n: # ensure proper substring
substr = s[i:j]
if set(substr) == gen_period:
minimal_substrings.add(substr)
# filter out non-minimal substrings
minimal_proper_substrings = set()
for substr in minimal_substrings:
is_minimal = True
for k in range(1, len(substr)):
if set(substr[:k]) == gen_period or set(substr[k:]) == gen_period:
is_minimal = False
break
if is_minimal:
minimal_proper_substrings.add(substr)
return minimal_proper_substrings
def count_minimal_unique_proper_substrings(s):
gen_period = generalized_period(s)
minimal_substrings = minimal_proper_substrings(s, gen_period)
return len(minimal_substrings)
import sys
input = sys.stdin.read
data = input().splitlines()
for line in data:
if line.strip():
result = count_minimal_unique_proper_substrings(line)
print(result)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 10412kb
input:
aabbabb abAB34aB3ba7 104001144 aaabcaaa a bb bd 1234567
output:
2 1 3 2 0 1 0 0
result:
ok 8 lines
Test #2:
score: 0
Accepted
time: 19ms
memory: 10808kb
input:
kejfASKDNF2342389fjsl2lsklsdflkjdKDFJKFD2342359829jdkjfkdklsjekfw234234234235123 11111111111111111111111111111111111111111111111111111111111111111111111111111111 12312343123123142312341234123412341234123423412312341234123232312341232341234123
output:
1 1 11
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 23ms
memory: 10760kb
input:
1234543212345432123454321234543212345432123454321234543212345432123454321 1234543212345432123454321234543212345432123454321234543212345432123454321Z a1234543212345432123454321234543212345432123454321234543212345432123454321 ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCD...
output:
2 1 1 6 1 1 25 2 1 1 1 0 0 1 1 4 5 2 1 1 1 1
result:
ok 22 lines
Test #4:
score: 0
Accepted
time: 57ms
memory: 10880kb
input:
0123456789ABCDEFEDCBA9876543210123456789ABCDEFEDCBA98765432123456789ABCDEFEDCBA abcdeadbedcacdebadecbdaecdbacebdcaebecadebacebdabecdcbeabedcebdadbcecbdaedbcacb 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZzyxwvutsrqponmlkjihgfedcbaqdKYJt2iHEL3vWFghr 99RBKQEBTBCA8WRSVNBSCGVZFLPTP7F29965694YAKW3B77CCFXCNEWRRL8...
output:
2 32 1 2 1 2 2 1 2 1 1 8 7 8 13 1 6 3 2 1 1 1
result:
ok 22 lines
Test #5:
score: 0
Accepted
time: 31ms
memory: 10672kb
input:
x dddddddgggggg dgdgdgdgdgdg ef1ef1e ef1ef1 abcbacbacab cabcbacbacabc kadksfkaddkdfakkjdfjdfasjdafhgdafsdasflalsdlkhdfhdasjklsadkjdafhklsajfghdasjkdg 1234567890 1234567890987654321 ssss aba ec26hb6a4l2wv3rm1ut7r9nxtejs5riidbxenodgipyjjuxtdwi3bykyhnauvv5gvws8r7fxdady7ek8 q3g12voqn3mewezr1jfoejpgh4vc4...
output:
0 1 2 3 3 5 5 6 0 2 1 2 1 1 1 1 1 1 1 7 4 1
result:
ok 22 lines