1 files changed, 113 insertions, 0 deletions
diff --git a/challenge-329/ysth/python/ch-2.py b/challenge-329/ysth/python/ch-2.py
new file mode 100644
index 0000000000..444e31c8d3
--- /dev/null
+++ b/challenge-329/ysth/python/ch-2.py
@@ -0,0 +1,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()