# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3 (ipykernel)
#     language: python
#     name: python3
# ---

# # Break a Palindrome
#
# https://leetcode.com/explore/challenge/card/september-leetcoding-challenge-2021/639/week-4-september-22nd-september-28th/3985/

palindrome = "abcde"


def break_palindrome(palindrome):
        i = 0
        while i <= int(len(palindrome)/2):
            if palindrome[i] != 'a':
                return palindrome[:i] + 'a' + palindrome[i+1:]
            i += 1

        if len(palindrome) == 1:
            return ""

        else:
            return palindrome[:-1] + 'b'


# # Longest Palindromic Substring
#
# https://leetcode.com/problems/longest-palindromic-substring/

s = "aaaaaaaaaababaddabab"
s = "babaddabab"


def longest_palindromic_subsr(s):
    ls = len(s)
    
    record = ""
    candidate_1 = ""
    candidate_2 = ""

    i = 0
    while i < ls:
        if i > ls - int(len(record)/2) + 1:
            break

        j = 0
        candidate_1 = ""
        while i-j>=0 and i+j<=ls-2 and s[i-j] == s[i+1+j]:
            candidate_1 = s[i-j]+candidate_1+s[i+1+j]
            j += 1

        k = 1
        candidate_2 = s[i]
        while i-k>=0 and i+k<=ls-1 and s[i+k] == s[i-k]:
            candidate_2 = s[i-k]+candidate_2+s[i+k]
            k += 1

        record = max(record, candidate_1, candidate_2, key=len)

        i += 1
    
    return record


longest_palindromic_subsr(s)

# # Longest Substring Without Repeating Characters
#
# https://leetcode.com/problems/longest-substring-without-repeating-characters/

s = "pabcwjwkeabcw"

import string
import random

{'a': True}

s = ''.join(random.choice(string.ascii_lowercase + string.digits) for _ in range(40000))

s = "<KEY>"


def longest_substtr(s):
    last_position = {}
    record = 0
 
    start_substr = 0
    i = 0
    while i < len(s):
        if s[i] in last_position:
            start_substr = max(start_substr, last_position[s[i]] + 1)

        record = max(record, i-start_substr + 1)
        last_position[s[i]] = i
        i += 1
 
    return record


longest_substtr(s)

# # N-th Tribonacci Number
#
# https://leetcode.com/explore/challenge/card/september-leetcoding-challenge-2021/639/week-4-september-22nd-september-28th/3986/

n = 5


def n_trib_num(n):
    if n == 0:
        return 0
    elif n in (1, 2):
        return 1
    else:
        n = n - 3
        r = [0, 1, 1]

        while n != 0:
            r.append(sum(r[-3:]))
            n -= 1
        
        return sum(r[-3:])


n_trib_num(4)

StarcoderdataJupyterScriptsDedupFiltered