import re
def find_paritions(lst, word, running=[]):
    for (index,item) in enumerate(lst):
        if index > 0:
            running.pop()
        running = running + [item]
        if item[1] == len(word):
            complete_paths.append(running)
            return
        to_explore = []
        end = item[1]
        for item_next in list_parition_index:
            if item_next[0] == end:
                to_explore.append(item_next)
        if len(to_explore) == 0:
            return
        find_paritions(to_explore,word,running)

    return complete_paths

complete_paths=[]
word = "ababbbabbababa"
start = 0
end = 1
parition_count =0
list_parition_index = []
for start in range (len(word)):
    end=start+1
    while end < len(word) + 1:
        if word[start:end] == word[start:end][::-1]:
            list_parition_index.append([start,end])
            end +=1
        else:
            end +=1
list_zeroes = [x for x in list_parition_index if x[0] == 0]


x = find_paritions (list_zeroes,word)
print(f"The total number of divisions required is {len(min(x,key=len))-1}")
print(min(x,key=len))

#Uses dynamic programming

def find_partitions(s: str) -> int:

        dp = [0]*len(s)
        for i in range(len(s)-2,-1,-1):
            dp[i] = 0 if s[i:]==s[i:][::-1] else 1 + min(dp[j] for j in range(i+1,len(s)) if s[i:j] == s[i:j][::-1])
        return dp[0]

def find_partitions_2(s: str) -> int:

    cut = [x for x in range(-1, len(s))]
    for i in range(0,len(s)):
        for j in range(i, len(s)):
            if s[i:j] == s[j:i:-1]:
                cut[j+1] = min(cut[j+1], cut[i]+1)
    return cut[-1]

#%timeit find_partitions("ababbbabbababa")
80.7 µs ± 17.1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

#%timeit find_partitions_2("ababbbabbababa")
66.9 µs ± 9.84 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

def find_partitions_3(s: str) -> int:

        if not s: return -1
        if s == s[::-1]: return 0
        length = len(s)
        for i in range(1, length):
            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                return 1
        output = [-1] + [i for i in range(length)]
        is_palindrome = [[False] * (i + 1) for i in range(length)]
        for i in range(length):
            for j in range(i + 1):
                if s[i] == s[j] and (i - j < 2 or is_palindrome[i - 1][j + 1]):
                    is_palindrome[i][j] = True
                    output[i + 1] = min(output[i + 1], output[j] + 1)
        return output[length]

#%timeit find_partitions_3("ababbbabbababa")
48.9 µs ± 3.65 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)