1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
import sys
from string import ascii_letters
import random
from enum import IntEnum
def longest_nice_substring(string: str) -> str:
# longest nice substring found so far
longest_nice_substring: str = ''
# characters that we know can't form part of a not yet found nice substring
never_nice: set[str] = set(string) - set(string.swapcase())
# loop over starting indexes while it is possible to find a longer nice substring
next_starting_index: int = 0
while len(string) - next_starting_index > len(longest_nice_substring):
starting_index: int = next_starting_index
c: str = string[starting_index]
next_starting_index += 1
# can we rule out any substring starting here?
if c in never_nice:
continue
# shortest substring that may be nice will end with the opposite character
ending_index: int = string.find(c.swapcase(), next_starting_index) + 1
if ending_index == 0:
never_nice.add(c)
continue
# what we know so far about substrings starting at this starting index
substring_prefix: str = string[starting_index:ending_index]
nice: set[str] = set(substring_prefix) & set(substring_prefix.swapcase())
not_yet_nice: set[str] = set(substring_prefix) - nice
# found a nice substring?
if not not_yet_nice:
if len(substring_prefix) > len(longest_nice_substring):
longest_nice_substring = substring_prefix
# any nice strings starting in the middle of or just after this nice
# string will also be nice if started at the beginning of it, so
# this iteration of the outer loop will find them and the next
# iteration can be farther on
next_starting_index = ending_index + 1
# look for longer nice substrings starting at this starting index
for ending_index in range(ending_index, len(string)):
c = string[ending_index]
# character we know there's no match for later?
if c in never_nice:
break
# character not yet seen in this substring?
if c not in nice and c not in not_yet_nice:
# completes an upper/lower pair?
c_opposite: str = c.swapcase()
if c_opposite in not_yet_nice:
not_yet_nice.remove(c_opposite)
nice.update(c, c_opposite)
else:
not_yet_nice.add(c)
# found a nice substring?
if not not_yet_nice:
if ending_index - starting_index >= len(longest_nice_substring):
longest_nice_substring = string[starting_index:ending_index+1]
# any nice strings starting in the middle of or just after this
# nice string will also be nice if started at the beginning of
# it, so this iteration of the outer loop will find them and the
# next iteration can be farther on
next_starting_index = ending_index + 2
return longest_nice_substring
def simple_longest_nice_substring(string: str) -> str:
longest_nice_substring: str = ''
for starting_index in range(0, len(string)):
nice: set[str] = set()
not_yet_nice: set[str] = set()
for ending_index in range(starting_index, len(string)):
c: str = string[ending_index]
if c not in nice and c not in not_yet_nice:
if c.swapcase() in not_yet_nice:
not_yet_nice.remove(c.swapcase())
nice.update(c, c.swapcase())
else:
not_yet_nice.add(c)
if not not_yet_nice and ending_index - starting_index + 1 > len(longest_nice_substring):
longest_nice_substring = string[starting_index:ending_index+1]
return longest_nice_substring
def main() -> None:
inputs: list[str] = sys.argv[1:]
# if given command line arguments, do those
if len(inputs):
for string in inputs:
print(f'{string:<30} -> {longest_nice_substring(string)}')
# otherwise, run an endless test of random values, comparing to simple version (stopping if an unexpected difference was found)
else:
checked: int = 0
while True:
checked += 1
string = ''.join(random.choice(ascii_letters) for i in range(random.randint(0,200)))
if simple_longest_nice_substring(string) != longest_nice_substring(string):
print(f'string: {string}\nsimple: {simple_longest_nice_substring(string)}\ncomplex: {longest_nice_substring(string)}')
break
if checked % 1000 == 0:
print(f'{checked}', end='\r')
if __name__ == '__main__':
main()
|
