Split a given string into 2 and/or 3 letter characters such that no two consecutive strings are duplicates of each other

two-three-consecutive_nonduplicate-split_string.py

"""
We can define 2 special types of strings (both consisting of lowercase English letters):

- two_string: string of length 2 (example: "ab","zz")
- three_string: string of length 3 (example: "abc","ghw")

You can create new strings by placing one or several two_strings and three_strings
side by side in a line and without placing two same strings next to one another.

From the example above you can create for example “abzz”, “ababc”, “zzabcghwab” etc.

Given a string S, think of all the ways in which that string S could have been built
with the above method and enumerate all the distinct two_strings and three_strings
you would need for all these different ways of building S. For example given a string
abcdef there are two ways to build (ab, cd, ef) (abc, def) so the list of distinct
strings is ['ab', 'cd', 'ef', 'abc', 'def'].

Write a function split_string() which, given a string S of length N, returns the list
of all distinct two_strings and three_strings that could be used for building S, and
an empty list if there is no solution.

Constraints:

N < 100

Adjacent two same strings are forbidden

Example:

>>> split_string("abcdef")
['ab', 'abc', 'cd', 'def', 'ef']

>>> split_string("abcdefg")
['ab', 'abc', 'cd', 'cde', 'de', 'efg', 'fg']

>>> split_string("ababcabc")
['aba', 'abc', 'bc', 'bca']

>>> split_string("ccccacccc")
['cac', 'ccc']
"""

from functools import cache
from typing import Union


class InvalidSplit(Exception):
    """Exception to be thrown when split is not possible"""

    pass


class SplitBoth:
    is2 = True
    is3 = True
    only2 = False
    only3 = False


class SplitTwo:
    is2 = True
    is3 = False
    only2 = True
    only3 = False


class SplitThree:
    is2 = False
    is3 = True
    only2 = False
    only3 = True


SplitOption = Union[SplitBoth, SplitTwo, SplitThree]


def _try_splitting(first: str, rest: str, try_split: SplitOption):
    try:
        return [first] + _split_string(rest, try_split)
    except InvalidSplit:
        return []


@cache
def _split_string(s: str, try_split: SplitOption = SplitBoth):
    size = len(s)

    if size == 0:
        return []

    if size == 1:
        raise InvalidSplit()

    if size in [2, 3]:
        if size == 2 and try_split.only3 or size == 3 and try_split.only2:
            raise InvalidSplit()
        return [s]

    value = []

    if try_split.is2:
        s2, s2r = s[:2], s[2:]
        if s2r.startswith(s2):
            value += _try_splitting(s2, s2r, SplitThree)
        else:
            value += _try_splitting(s2, s2r, SplitBoth)

    if try_split.is3:
        s3, s3r = s[:3], s[3:]
        if s3r.startswith(s3):
            value += _try_splitting(s3, s3r, SplitTwo)
        else:
            value += _try_splitting(s3, s3r, SplitBoth)

    if value:
        return value

    raise InvalidSplit()


def split_string(s):
    """This is the main function"""
    try:
        return sorted(set(_split_string(s, SplitBoth)))
    except InvalidSplit:
        return []


if __name__ == "__main__":
    import doctest

    # Run all tests when called from CLI
    print(doctest.testmod())