# Longest Palindromic Substring (Linear)

A palindrome is a word, phrase, or sequence that reads the same backward as forward, e.g.,
'madam' or 'racecar'. Even the letter 'x' is considered a palindrome. 

For this Kata, you are given a string ```s```. Write a function that returns the longest _contiguous_ palindromic substring in ```s``` (it could be the entire string). In the event that there are multiple longest palindromic substrings, return the first to occur.

I'm not trying to trick you here:
- You can assume that all inputs are valid strings.
- Only the letters a-z will be used, all lowercase (your solution should, in theory, extend to more than just the letters a-z though). 

**NOTE:** Quadratic asymptotic complexity _(O(N^2))_ or above will __NOT__ work here.

-----

## Examples

### Basic Tests

```
Input: "babad"
Output: "bab"
(Note: "bab" occurs before "aba")
```
```
Input: "abababa"
Output: "abababa"
```
```
Input: "cbbd"
Output: "bb"
```

### Edge Cases

```
Input: "ab"
Output: "a"
```
```
Input: ""
Output: ""
```
-----

## Testing

Along with the example tests given:

 - There are **500** tests using strings of length in range [1 - 1,000]
 - There are **50** tests using strings of length in range [1,000 - 10,000]
 - There are **5** tests using strings of length in range [10,000 - 100,000]
 
All test cases can be passed within 10 seconds, but non-linear solutions will time out every time. _Linear performance is essential_. 

## Good Luck!

-----

This problem was inspired by [this](https://leetcode.com/problems/longest-palindromic-substring/) challenge on LeetCode. Except this is the performance version :^)

Difficulty: interview

Starter code:

def longest_palindrome(s):
	

Solutions:
'''
    Write a function that returns the longest contiguous palindromic substring in s. 
    In the event that there are multiple longest palindromic substrings, return the 
    first to occur.
'''

def longest_palindrome(s, sep=" "):
    # Interpolate some inert character between input characters
    # so we only have to find odd-length palindromes
    t = sep + sep.join(s) + sep

    r = 0       # Rightmost index in any palindrome found so far ...
    c = 0       # ... and the index of the centre of that palindrome.
    spans = []  # Length of the longest substring in T[i:] mirrored in T[i::-1]

    # Manacher's algorithm
    for i,_ in enumerate(t):
        span = min(spans[2*c-i], r-i-1) if i < r else 0
        while span <= i < len(t)-span and t[i-span] == t[i+span]:
            span += 1
        r, c = max((r, c), (i+span, i))
        spans.append(span)

    span = max(spans)
    middle = spans.index(span)

    return t[middle-span+1:middle+span].replace(sep, "") 

def longest_palindrome(s):
    """"Based on Manacher algorithm"""

    if s=="":
        t = "^#$"
    else:
        t = "^#" + "#".join(s) + "#$"

    c = 0
    r = 0
    p = [0] * len(t)

    for i in range(1,len(t)-1):
    
        mirror = 2*c - i
        p[i] = max(0, min(r-i, p[mirror]))
        
        while t[i+1+p[i]] == t[i-1-p[i]]:
            p[i] += 1

        if i+p[i] > r:
            c = i
            r = i+p[i]

    k, i = 0,0
    for j,e in enumerate(p):
        if e > k:
            k, i = e, j
            
    deb, fin = ((i-k)//2, (i+k)//2)
    return s[deb:fin]

'''
    Write a function that returns the longest contiguous palindromic substring in s. 
    In the event that there are multiple longest palindromic substrings, return the 
    first to occur.
'''

# TODO: Complete in linear time xDD
def longest_palindrome(s):
    if is_palindrome(s):
        return s
        
    max_pal = ''

    for i in range(len(s)):
        temp = check(i, i, s)
        if len(max_pal) < len(temp):
            max_pal = temp

    return max_pal


def check(li, ri, s):
    if li > 0 and ri < len(s):
        if is_palindrome(s[li - 1: ri + 2]):
            return check(li - 1, ri + 1, s)
        elif is_palindrome(s[li: ri + 2]):
            return check(li, ri + 1, s)
        elif is_palindrome(s[li - 1: ri + 1]):
            return check(li - 1, ri, s)

    return s[li: ri + 1]


def is_palindrome(s):
    return s == s[::-1]

'''
    Write a function that returns the longest contiguous palindromic substring in s. 
    In the event that there are multiple longest palindromic substrings, return the 
    first to occur.
'''
import re

def longest_palindrome(string):
    if len(string) < 2:
        return string
    string = '|' + '|'.join(string) + '|'
    LPS = [0 for _ in range(len(string))]
    C = 0
    R = 0

    for i in range(len(string)):
        iMirror = 2 * C - i
        if R > i:
            LPS[i] = min(R - i, LPS[iMirror])
        else:
            LPS[i] = 0
        try:
            while string[i + 1 + LPS[i]] == string[i - 1 - LPS[i]]:
                LPS[i] += 1
        except:
            pass

        if i + LPS[i] > R:
            C = i
            R = i + LPS[i]

    r, c = max(LPS), LPS.index(max(LPS))
    return string[c - r: c + r].replace("|", "")


def modi(s):
    return ''.join(['#'+i for i in s]) + '#'

def demodi(s):
    return ''.join(([i for i in s if i != '#']))

def longest_palindrome(s):
    s = modi(s)
    lenth, c, r, maxl, p = len(s), 0, 0, 0, [0]*len(s)

    for i in range(lenth):
        mir = (2*c) - i

        if i<r: 
            p[i] = min(r-i, p[mir])

        a, b = i + (1+p[i]), i - (1+p[i])
        while a < lenth and b >= 0 and s[a] == s[b]:
            p[i] += 1
            a += 1
            b -= 1

        if (i + p[i]) > r: 
            c = i
            r = i + p[i]

            if p[i] > maxl: 
                maxl = p[i]
    mai = p.index(maxl)
    return demodi(s[mai-maxl: mai+maxl+1])

def get_func(s, i):
    p2, p3 = '', ''
    s2, s3 = s[i:i+2], s[i: i+3]
    if s2[0] == s2[-1]:
        p2 = s2
        u, v = i-1, i+2
        while(u > -1 and v < len(s)):
            if s[u] != s[v]:
                break
            p2 = s[u] + p2 + s[v]
            u, v = u-1, v+1
    if s3[0] == s3[-1]:
        p3 = s3
        u, v = i-1, i+3
        while(u > -1 and v < len(s)):
            if s[u] != s[v]:
                break
            p3 = s[u] + p3 + s[v]
            u, v = u-1, v+1
    return p3 if len(p3) > len(p2) else p2

def set_pal(p, idxp, pal, idx):
    if len(p) > len(pal) or (len(p) == len(pal) and idxp < idx):
        pal, idx = p, idxp
    return pal, idx

def longest_palindrome(s):
    if len(s) < 2: return s
    pal = s[0] # b
    idx = 1
    j = len(s) // 2 - 1
    k = j + 1
    if len(s) > 3:
        for i in range(j):
            pal, idx = set_pal(get_func(s, j-i-1), j-i, pal, idx)
            pal, idx = set_pal(get_func(s, k+i-1), k+i, pal, idx)
            if len(s) < len(pal) + 2*i:
                break
    if len(pal) < 3 and len(s) % 2 != 0:
        pal, idx = set_pal(get_func(s, len(s)-3), len(s)-2, pal, idx)
    if len(pal) < 2:
        sub = s[len(s)-2:len(s)]
        if sub[0] == sub[-1]:
            pal = sub
    return pal

def longest_palindrome(s):
    s = "_" + '_'.join(s) + "_"
    n = len(s)
    a = [0] * n

    rb = ml = mctr = ctr = c = 0

    for i in range(1,n):
        a[i] = min(rb-i, a[2*ctr-i]) if rb > i else 1
        c = a[i]
        while i+c < n and i >= c and s[i-c] == s[i+c]: c += 1
        a[i] = c
        if i+c > rb:
            rb = i+c
            ctr = i
        if c > ml:
            ml = c
            mctr = i

    return s[mctr-ml+1 : mctr+ml].replace('_', "")

def longest_palindrome(S):
    """
    O(n) algorithm to find longest palindrome substring
    :param S: string to process
    :return: longest palindrome
    """

    # Create a copy of array with sentinel chars in between and around
    # Also include space for starting and ending nodes
    T = [0] * (2 * (len(S)) + 3)

    # Fill odd indices with sentinel chars evens with real chars
    sen_char = "@"
    start_sen = "!"
    end_sen = "#"
    for i in range(len(T)):
        if i == 0:
            T[i] = start_sen
        elif i % 2 == 0 and i < len(T) - 1:
            s_index = (i - 1) // 2
            T[i] = S[s_index]
        elif i % 2 == 1 and i < len(T) - 1:
            T[i] = sen_char
        else:
            T[i] = end_sen

    # Also track the expand length around all indices
    P = [0] * len(T)

    # Track center of largest palin yet
    # and its right boundary
    center = right = 0

    # Track largest expansion length
    # and it index
    max_len = index = 0

    # Loop through word array to
    # update expand length around each index
    for i in range(1, len(T) - 1):

        # Check to see if new palin
        # around i lies within a bigger one
        # If so, copy expand length of its mirror
        mirror = 2 * center - i
        if i < right:
            P[i] = min(right - i, P[mirror])

        # Expand around new center
        # Update expand length at i as needed
        while T[i + P[i] + 1] == T[i - (P[i] + 1)]:
            P[i] += 1

        # If we breached previous right boundary
        # Make i the new center of the longest palin
        # and update right boundary
        if i + P[i] > right:
            right = i + P[i]
            center = i

        # Update max_len
        if P[i] > max_len:
            max_len = P[i]
            index = i

    t_arr = T[ index - max_len: index + max_len + 1 ]
    word_arr = [ c for c in t_arr if c != sen_char and c != start_sen and c != end_sen ]
    word = "".join(word_arr)

    return word

def longest_palindrome(s):
    n = len(s)
    if n <= 1:
        return s
    max, index = 0,  -1
    max2, index2 = 0, -1
    d1 = [0]*n
    i, l, r = 0, 0, -1
    while i < n:
        if i > r:
            k = 1
        else:
            k = min(d1[l + r - i], r - i + 1)
        while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:
            k += 1
        if k > max:
            max, index = k, i  # s[i-k+1:i+k], 2k-1
        d1[i] = k
        k -= 1
        if i + k > r:
            l, r = i - k, i + k
        i += 1

    d2 = [0]*n
    i, l, r = 0, 0, -1
    while i < n:
        if i > r:
            k = 0
        else:
            k = min(d2[l + r - i + 1], r - i + 1)
        while 0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k]:
            k += 1
        if k > max2:
            max2, index2 = k, i  # s[i-k:i+k], 2k
        d2[i] = k
        k -= 1
        if i + k > r:
            l, r = i - k - 1, i + k
        i += 1

    index = index - max + 1  # start
    max = 2 * max - 1        # len
    index2 -= max2           # start
    max2 *= 2                # len
    start, ln = 0, 0
    if max == max2:
        if index <= index2:
            start, ln = index, max
        else:
            start, ln = index2, max2
    elif max > max2:
        start, ln = index, max
    else:
        start, ln = index2, max2
    return s[start: start + ln]


def longest_palindrome(s):
    tst = '#'.join('^{}$'.format(s))
    n = len(tst)
    p = [0] * n
    c = 0
    r = 0
    for i in range (1, n - 1):
        p[i] = r > i and min(r-i, p[2*c-i])
        while tst[i+1+p[i]] == tst[i-1-p[i]]:
            p[i] += 1
        if i + p[i] > r:
            c, r = i, i + p[i]
    mx, ctri = max((n, -i) for i, n in enumerate(p))
    return s[(-ctri-mx)//2:(-ctri+mx)//2]