Jovian
⭐️
Sign In
Learn data science and machine learning by building real-world projects on Jovian

Longest Palindromic Substring

How to run the code and save your work

The recommended way to run this notebook is to click the "Run" button at the top of this page, and select "Run on Binder". This will run the notebook on mybinder.org, a free online service for running Jupyter notebooks.

This tutorial is an executable Jupyter notebook. You can run this tutorial and experiment with the code examples in a couple of ways: using free online resources (recommended) or on your computer.

Option 1: Running using free online resources (1-click, recommended)

The easiest way to start executing the code is to click the Run button at the top of this page and select Run on Binder. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

Option 2: Running on your computer locally

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

Saving your work

Before staring the assignment, let's save a snapshot of the assignment to your Jovian profile, so that you can access it later, and continue your work.

In [1]:
project_name = 'final-project-longest-palindromic-substring' # give it an appropriate name
In [2]:
!pip install jovian --upgrade --quiet
In [3]:
import jovian
In [4]:
jovian.commit(project=project_name)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

Problem Statement

Given a string s, return the longest palindromic substring in s.

Source: https://leetcode.com/problems/longest-palindromic-substring/

The Method

Here's the systematic strategy we'll apply for solving problems:

  1. State the problem clearly. Identify the input & output formats.
  2. Come up with some example inputs & outputs. Try to cover all edge cases.
  3. Come up with a correct solution for the problem. State it in plain English.
  4. Implement the solution and test it using example inputs. Fix bugs, if any.
  5. Analyze the algorithm's complexity and identify inefficiencies, if any.
  6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

Solution

1. State the problem clearly. Identify the input & output formats.

While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear for you.

Problem

Given a string s, get the longest palindromic substring from s

  1. A substring is a contiguous sequence of characters within a string.
  2. There're two kinds of palindrome: even and odd

Example : aba and aa


Input

  1. str : the given string

(add more if required)

Output

  1. s : the longest palindromic substring

(add more if required)


Based on the above, we can now create a signature of our function:

In [5]:
def basicLongestPalindSubstring(str):
    pass

Save and upload your work before continuing.

In [6]:
import jovian
In [7]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

2. Come up with some example inputs & outputs. Try to cover all edge cases.

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

  1. A string with basic odd palindromic substring
  2. A string with basic even palindromic substring
  3. A string with no palindromic substring
  4. A string with multi palindromic substring with same length (longest)
  5. An empty string
  6. A string with only one character
  7. The given string is also the palindromic substring

(add more if required)

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: input (a dictionary itself containing one key for each argument to the function and output (the expected result from the function).

In [8]:
test0 = {
    'input': {
        'str' : 'abcbaefgh'
    },
    'output': 'abcba'
}
In [9]:
test1 = {
    'input': {
        'str' : 'abbaefgh'
    },
    'output': 'abba'
}
In [10]:
test2 = {
    'input': {
        'str' : 'abcdefghijkmn'
    },
    'output': 'a'
}
In [11]:
test3 = {
    'input': {
        'str' : 'babad'
    },
    'output': 'bab' # or 'aba'
}
In [12]:
test4 = {
    'input': {
       'str' : ''
    },
    'output': ''
}
In [13]:
test5 = {
    'input': {
        'str' : 'e'
    },
    'output': 'e'
}
In [14]:
test6 = {
    'input': {
        'str' : 'aaaaaaaa'
    },
    'output': 'aaaaaaaa'
}
In [15]:
test7 = {
    'input': {
        'str' : 'aaaabaaaa'
    },
    'output': 'aaaabaaaa'
}

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called tests.

In [16]:
tests = [test0, test1, test2, test3, test4, test5, test6, test7]
In [ ]:
 

3. Come up with a correct solution for the problem. State it in plain English.

Our first goal should always be to come up with a correct solution to the problem, which may not necessarily be the most efficient solution. Come with a correct solution and explain it in simple words below:

Brute Force :

The easiest and simplest solution we can find right away is brute force.

  1. Find all the substring in the given string
  2. Check if it's a palindromic string or not
  3. Find the longest palindromic substring

(add more steps if required)

Let's save and upload our work before continuing.

In [17]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

4. Implement the solution and test it using example inputs. Fix bugs, if any.

In [18]:
def isPalindrome(str):
    
    low = 0
    high = len(str)-1
    
    while low<=high:
        if str[low] != str[high]: 
          return False
        low = low + 1
        high= high - 1
        
    return True
In [19]:
def basicLongestPalindSubstring(str):
    maxLength = -1
    result = ''
    for i in range(len(str)):
        for j in range(i,len(str)):
            subStr = str[i:j+1]
            if isPalindrome(subStr) and len(subStr) > maxLength:
                result = subStr
                maxLength = len(subStr)
                
    return result
            
In [ ]:
 
In [ ]:
 

We can test the function by passing the input to it directly or by using the evaluate_test_case function from jovian.

In [20]:
from jovian.pythondsa import evaluate_test_case
In [21]:
evaluate_test_case(basicLongestPalindSubstring,test0)
Input: {'str': 'abcbaefgh'} Expected Output: abcba Actual Output: abcba Execution Time: 0.027 ms Test Result: PASSED
Out[21]:
('abcba', True, 0.027)

Evaluate your function against all the test cases together using the evaluate_test_cases (plural) function from jovian.

In [22]:
from jovian.pythondsa import evaluate_test_cases
In [23]:
evaluate_test_cases(basicLongestPalindSubstring, tests)
TEST CASE #0 Input: {'str': 'abcbaefgh'} Expected Output: abcba Actual Output: abcba Execution Time: 0.04 ms Test Result: PASSED TEST CASE #1 Input: {'str': 'abbaefgh'} Expected Output: abba Actual Output: abba Execution Time: 0.035 ms Test Result: PASSED TEST CASE #2 Input: {'str': 'abcdefghijkmn'} Expected Output: a Actual Output: a Execution Time: 0.065 ms Test Result: PASSED TEST CASE #3 Input: {'str': 'babad'} Expected Output: bab Actual Output: bab Execution Time: 0.019 ms Test Result: PASSED TEST CASE #4 Input: {'str': ''} Expected Output: Actual Output: Execution Time: 0.003 ms Test Result: PASSED TEST CASE #5 Input: {'str': 'e'} Expected Output: e Actual Output: e Execution Time: 0.01 ms Test Result: PASSED TEST CASE #6 Input: {'str': 'aaaaaaaa'} Expected Output: aaaaaaaa Actual Output: aaaaaaaa Execution Time: 0.051 ms Test Result: PASSED TEST CASE #7 Input: {'str': 'aaaabaaaa'} Expected Output: aaaabaaaa Actual Output: aaaabaaaa Execution Time: 0.051 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[23]:
[('abcba', True, 0.04),
 ('abba', True, 0.035),
 ('a', True, 0.065),
 ('bab', True, 0.019),
 ('', True, 0.003),
 ('e', True, 0.01),
 ('aaaaaaaa', True, 0.051),
 ('aaaabaaaa', True, 0.051)]

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

Let's save our work before continuing.

In [24]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring
In [ ]:
 

5. Analyze the algorithm's complexity and identify inefficiencies, if any.

Looking at the code we have two for loop which is n^2 and a while loop to check if the substring is a palindromic string.

So the algorithm's complexcity is n^3

In [25]:
basic_time_complexity = 'O(n^3)'

Because we only use a variable to store the string so the algorithms's space complexcity is 1

In [26]:
basic_space_complexity = 'O(1)'
In [27]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

It's easy to see why the algorithm is so ineffective.

  1. Each character of the string is a palindromic so we don't need to call and check the substring
  2. If the string length is 2 then we just need to check str[0] and str[1]
  3. If the string length is 3 or more: If the length == 3 we check str[0] and str[2] else We need to check if it's palindromic or and to decrease the complexcity we need to devide it to smaller problem.

This suggests the use of dynamic programming here.

In [28]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

7. Come up with a correct solution for the problem. State it in plain English.

Come with the optimized correct solution and explain it in simple words below:

Dynamic Programming:
  1. Create a table (t) with the row (i) and column (j) equal to string length

  2. Fill the table follow the rule : (look at the picture below)

    Base case 1 : Each substring with length == 1 is a palindromic so all t[i][j] is true

    Base case 2 : Check if adjacent characters in a string make a palindrome t[i] == t[i+1] then set the t[i][i+1] to true

    Base case 3 : If length >= 3 then the substring from i to j is a palindrome if t[i] == t[j] and every substring t[i+1] == t[j-1] and so on which already calculated before

Let's save and upload our work before continuing.

In [29]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring
In [ ]:
 

8. Implement the solution and test it using example inputs. Fix bugs, if any.

In [30]:
def dpLongestPalindSubstring(str):
    
    if len(str) == 0:
        return ''
    
    maxLength = 1 
    start = 0
    result = ''
    n = len(str)
    table = [[0 for x in range(n)] for y in range(n)]
    
    #base 1 : t[i][j] = true
    for i in range (n):
        for j in range (n):
            if i == j:
                table[i][j] = 1
                
    
    #base 2 : check adjacent characters    
    for i in range(n - 1):
        if str[i] == str[i+1]:
            table[i][i+1] = 1
            start = i
            maxLength = 2
            
    #base 3 : length > 3
    for length in range (3, n+1):
        for i in range (0, n - length + 1):
            j = i + length - 1
            if (str[i] == str[j] and table[i+1][j-1] == 1):
                table[i][j] = 1
                if (length > maxLength):
                    start = i
                    maxLength = length

    result = str[start : start + maxLength]
    print(maxLength)
    print(result)
                
    return result
In [31]:
dpLongestPalindSubstring('abbaefgh')
4 abba
Out[31]:
'abba'
In [32]:
evaluate_test_cases(dpLongestPalindSubstring, tests)
TEST CASE #0 5 abcba Input: {'str': 'abcbaefgh'} Expected Output: abcba Actual Output: abcba Execution Time: 0.21 ms Test Result: PASSED TEST CASE #1 4 abba Input: {'str': 'abbaefgh'} Expected Output: abba Actual Output: abba Execution Time: 0.06 ms Test Result: PASSED TEST CASE #2 1 a Input: {'str': 'abcdefghijkmn'} Expected Output: a Actual Output: a Execution Time: 0.53 ms Test Result: PASSED TEST CASE #3 3 bab Input: {'str': 'babad'} Expected Output: bab Actual Output: bab Execution Time: 0.068 ms Test Result: PASSED TEST CASE #4 Input: {'str': ''} Expected Output: Actual Output: Execution Time: 0.002 ms Test Result: PASSED TEST CASE #5 1 e Input: {'str': 'e'} Expected Output: e Actual Output: e Execution Time: 0.048 ms Test Result: PASSED TEST CASE #6 8 aaaaaaaa Input: {'str': 'aaaaaaaa'} Expected Output: aaaaaaaa Actual Output: aaaaaaaa Execution Time: 0.081 ms Test Result: PASSED TEST CASE #7 9 aaaabaaaa Input: {'str': 'aaaabaaaa'} Expected Output: aaaabaaaa Actual Output: aaaabaaaa Execution Time: 0.073 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[32]:
[('abcba', True, 0.21),
 ('abba', True, 0.06),
 ('a', True, 0.53),
 ('bab', True, 0.068),
 ('', True, 0.002),
 ('e', True, 0.048),
 ('aaaaaaaa', True, 0.081),
 ('aaaabaaaa', True, 0.073)]
In [33]:
dpLongestPalindSubstring('bb')
2 bb
Out[33]:
'bb'
In [34]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

The dynamic programming algorimth need to loop to run so we have complexity of O(n^2)

In [35]:
basic_time_complexity = 'O(n^2)'

It also requires addition n * n space to create a table and store data.

In [36]:
basic_space_complexity = 'O(n^2)'
In [37]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

10. Another approach

Looking again we find out that space and complexity 0(n^2) is still not a good optimization. But to better than n^2 it should be O(nlogn) or O(n).

For O(nlogn) we can see that its a bit similar to quick sort and we can find a palindromic substring at the center first then follow along left and right. Even better if the palindrome found at the center has a length of k then we can consider ignore any other substring with length < k.

  1. Loop through the string
  2. At each position find the longest palindrome with the center is the position index
  3. Compare and get the longest palindrome
In [38]:
def expandedPalindStr(str, low, high):
    
    while low >= 0 and high < len(str) and str[low] == str[high]:
        low = low - 1
        high = high + 1
        
    return str[low + 1:high]

In [39]:
def optimizedLongestPalindSubstring(str):
    result = ''
    length = len(str)
    maxLength = 0
   
    for i in range(length):
        
        remainLength = length - i
        
        # if remainLength < maxLength / 2 (since we expand from both size) then we dont need to check the palindromic length anymore
        if remainLength < maxLength // 2:
            break            
        
        #assume i is the middle point of a palindrome and this is an even palindrome
        subStr = expandedPalindStr(str, i, i) 
        
        if (len(subStr) > maxLength):
            result = subStr
            maxLength = len(subStr)
            
        #assume i is the middle point of a palindrome and this is an odd palindrome
        subStr = expandedPalindStr(str, i, i + 1) 
        
        if (len(subStr) > maxLength):
            result = subStr
            maxLength = len(subStr)
    
    return result
    
In [40]:
evaluate_test_cases(optimizedLongestPalindSubstring, tests)
TEST CASE #0 Input: {'str': 'abcbaefgh'} Expected Output: abcba Actual Output: abcba Execution Time: 0.024 ms Test Result: PASSED TEST CASE #1 Input: {'str': 'abbaefgh'} Expected Output: abba Actual Output: abba Execution Time: 0.019 ms Test Result: PASSED TEST CASE #2 Input: {'str': 'abcdefghijkmn'} Expected Output: a Actual Output: a Execution Time: 0.028 ms Test Result: PASSED TEST CASE #3 Input: {'str': 'babad'} Expected Output: bab Actual Output: bab Execution Time: 0.015 ms Test Result: PASSED TEST CASE #4 Input: {'str': ''} Expected Output: Actual Output: Execution Time: 0.002 ms Test Result: PASSED TEST CASE #5 Input: {'str': 'e'} Expected Output: e Actual Output: e Execution Time: 0.005 ms Test Result: PASSED TEST CASE #6 Input: {'str': 'aaaaaaaa'} Expected Output: aaaaaaaa Actual Output: aaaaaaaa Execution Time: 0.021 ms Test Result: PASSED TEST CASE #7 Input: {'str': 'aaaabaaaa'} Expected Output: aaaabaaaa Actual Output: aaaabaaaa Execution Time: 0.023 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[40]:
[('abcba', True, 0.024),
 ('abba', True, 0.019),
 ('a', True, 0.028),
 ('bab', True, 0.015),
 ('', True, 0.002),
 ('e', True, 0.005),
 ('aaaaaaaa', True, 0.021),
 ('aaaabaaaa', True, 0.023)]
In [41]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

11. Analyze the algorithm's complexity

With this approach the worst case still get us to O(n^2) but we don't need any extra space so the space is reduce to 0(1)

In [42]:
optimized_time_complexity = 'O(n^2)'
In [43]:
optimized_space_complexity = 'O(1)'
In [45]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring

This algorithm is a bit similar to the algorithm above where you need to calculate the longest palindrome from a position i. But it replies on the characteric of palindrome that is symmetric around the center. So we can reuse precomputed data when a palindrome exists inside another palindrome.

  1. Create a new string S' that insert a unique character like '|' into even position. This will help us avoid the odd /even situation

  2. Create an array P with length = length of the new string. This array use to store the max length of palindrome at each position

  3. loop through the new string S'

  4. We have :

     C is the center of the palindrome
     R is radius of the palindrome start from 0
     i and mirr_i (mirror of i aka i' = 2*C-i) are the position that will be loop from start to end
    
  5. Follow the rule :

     if P[ i’ ] ≤ R – i,
     then P[ i ] ← P[ i’ ]
     else P[ i ] ≥ P[ i’ ]. (Which we have to expand past the right edge (R) to find P[ i ].
    
  6. If the palindrome centered at i does expand past R, we update C to i, (the center of this new palindrome), and extend R to the new palindrome’s right edge.

In [49]:
def modifyStr(str):
    if len(str) == 0:
        return '||'
    
    newStr = ''
    for i in range(len(str)):
        newStr += '|' + str[i]
        
    newStr += '|'
    return newStr
        
In [92]:
def manacherLongestPalindSubstring(str):
    newStr = modifyStr(str)
    print(newStr)
    p = [0] * len(newStr)
    center = 0
    radius = 0
    
    for i in range(len(newStr)):
        
        mirr_i = 2 * center - i
        
        if radius > i:
            p[i] = min(radius - i, p[mirr_i])
        else:
            p[i] = 0
        try:
            while newStr[i + p[i] + 1] == newStr[i - (p[i] + 1)]:
                p[i] += 1
        except:
            pass
            
        if i + p[i] > radius:
            center = i
            radius = i + p[i]
    print(p)
    
    maxLength, start = max(p), p.index(max(p))

    return newStr[start - maxLength : start + maxLength].replace('|','')
    
In [93]:
evaluate_test_cases(manacherLongestPalindSubstring, tests)
TEST CASE #0 |a|b|c|b|a|e|f|g|h| [0, 1, 0, 1, 0, 5, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] Input: {'str': 'abcbaefgh'} Expected Output: abcba Actual Output: abcba Execution Time: 0.089 ms Test Result: PASSED TEST CASE #1 |a|b|b|a|e|f|g|h| [0, 1, 0, 1, 4, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] Input: {'str': 'abbaefgh'} Expected Output: abba Actual Output: abba Execution Time: 0.084 ms Test Result: PASSED TEST CASE #2 |a|b|c|d|e|f|g|h|i|j|k|m|n| [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] Input: {'str': 'abcdefghijkmn'} Expected Output: a Actual Output: a Execution Time: 0.069 ms Test Result: PASSED TEST CASE #3 |b|a|b|a|d| [0, 1, 0, 3, 0, 3, 0, 1, 0, 1, 0] Input: {'str': 'babad'} Expected Output: bab Actual Output: bab Execution Time: 0.086 ms Test Result: PASSED TEST CASE #4 || [1, 0] Input: {'str': ''} Expected Output: Actual Output: Execution Time: 0.066 ms Test Result: PASSED TEST CASE #5 |e| [0, 1, 0] Input: {'str': 'e'} Expected Output: e Actual Output: e Execution Time: 0.068 ms Test Result: PASSED TEST CASE #6 |a|a|a|a|a|a|a|a| [0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0] Input: {'str': 'aaaaaaaa'} Expected Output: aaaaaaaa Actual Output: aaaaaaaa Execution Time: 0.12 ms Test Result: PASSED TEST CASE #7 |a|a|a|a|b|a|a|a|a| [0, 1, 2, 3, 4, 3, 2, 1, 0, 9, 0, 1, 2, 3, 4, 3, 2, 1, 0] Input: {'str': 'aaaabaaaa'} Expected Output: aaaabaaaa Actual Output: aaaabaaaa Execution Time: 0.13 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[93]:
[('abcba', True, 0.089),
 ('abba', True, 0.084),
 ('a', True, 0.069),
 ('bab', True, 0.086),
 ('', True, 0.066),
 ('e', True, 0.068),
 ('aaaaaaaa', True, 0.12),
 ('aaaabaaaa', True, 0.13)]

13. Analyze the algorithm's complexity

In each step, there are two possibilities. If p[i] ≤ r – i, we set p[i] to p[i’] which takes exactly one step. Otherwise we attempt to change the palindrome’s center to i by expanding it starting at the right edge, R. Extending R (the inner while loop) takes at most a total of N steps, and positioning and testing each centers take a total of N steps too. Therefore, this algorithm guarantees to finish in at most 2*N steps, giving a linear time solution.

So we have the algorithm's complexity at follow:

In [97]:
manacher_time_complexity = 'O(n)'
In [98]:
manacher_space_complexity = 'O(n)'
In [100]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "indexkyou/final-project-longest-palindromic-substring" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/indexkyou/final-project-longest-palindromic-substring
In [ ]:
jovian.submit(assignment="pythondsa-project")
[jovian] Attempting to save notebook..
In [ ]: