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

# the idea is we find all longest substrings and check them if any of them is palindromic
s = 'babad'
# - > 'bab or 'aba'

# brute force - O(n^3)
def longest_palindromic(s):
    longest = ''
    n = len(s)
    for i in range(n):
        for j in range(i+1, n):
            ss = s[i:j]
            if ss == ss[::-1] and len(ss) > len(longest):
                longest = ss
    return longest


longest_palindromic('ababaad')


# +
def longestPalindrome(s: str) -> str:
    n = len(s)
    longest = ''
    for i in range(n):
        # char at index i is the center - odd
        ss = findPalindromeAt(s, i, i)
        if(len(ss) > len(longest)):
            longest = ss
        
        # between chars at i and i+1 is the center - even
        ss = findPalindromeAt(s, i, i+1)
        if(len(ss) > len(longest)):
            longest = ss

    return longest

def findPalindromeAt(s, i1, i2):
    #print(f'in: {i1},{i2}')
    while i1 >= 0 and i2 < len(s) and s[i1] == s[i2]:
        i1 -= 1
        i2 += 1
    #print(f'out: {s[i1+1:i2]}')
    return s[i1+1:i2]


# -

longestPalindrome('abababd')


# +
# same solution, more concise (a bit more confusing)
def longestPalindrome(s: str) -> str:
    longest = ''
    for i in range(len(s)):
        for j in range(2):
            # chars at index i and i+j is the center
            ss = findPalindromeAt(s, i, i + j)
            if(len(ss) > len(longest)):
                longest = ss
    return longest

def findPalindromeAt(s, i1, i2):
    #print(f'in: {i1},{i2}')
    while i1 >= 0 and i2 < len(s) and s[i1] == s[i2]:
        i1 -= 1
        i2 += 1
    #print(f'out: {s[i1+1:i2]}')
    return s[i1+1:i2]


# -

longestPalindrome('ababababababab')



StarcoderdataJupyterScriptsDedupFiltered