Good afternoon! Here's our prompt for today.

We're given a string that's a mixture of several alphabetical characters.

JAVASCRIPT

1const str = "algototheehtotdaily";

Could you write a method to find the longest substring that is considered a palindrome? In the above example, it would be "totheehtot".

Where there are multiple longest palindromic substrings of the same length, for example in "abracadabra" ("aca" and "ada"), return the first to appear.

Constraints

The string can be empty, in which case return an empty string
The string will consist of only lowercase alphabets
Expected time complexity : O(n^2)
Expected space complexity : O(n^2)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx
    'PASSED: ' + "`longestPalindrome('nasduhuuhdousan')` should return `'huuh'`"
 
var assert = require('assert');
​
const longestPalindrome = (str) => {
  // fill in
  return '';
};
​
try {
  assert.equal(longestPalindrome(''), '');
​
  console.log('PASSED: ' + "`longestPalindrome('')` should return `''`");
} catch (err) {
  console.log(err);
}
​
try {
  assert.equal(longestPalindrome('algodaily'), 'a');
​
  console.log(
    'PASSED: ' + "`longestPalindrome('algodaily')` should return `'a'`"
  );
} catch (err) {
  console.log(err);
}
​
try {
  assert.equal(longestPalindrome('gymmyg'), 'gymmyg');
​
  console.log(

We'll now take you through what you need to know.

How do I use this guide?

Longest Palindromic Substring

I have a sister named "Maham". For my cousins and I, her name was fascinating, as it is the same spelling if we read it backwards and forwards.

Later on, as I grew up, I came to know that this interest is a problem in the field of Computer Science. Yes, you guessed it right, I'm talking about the study of palindromes.

In Computer Science, the palindrome problem has always been tricky. We have to find a solution for a word that reads the same backward as read forward keeping the solution optimized. Don’t worry ,once you’ll get the concept, it will become easy for you to deal with any problem related to palindromes.

We will take you on a journey where you will learn about the longest palindromic substring. A palindromic substring is a substring which is a palindrome. Let’s say that we have a string ‘"Maham"’-- the longest palindromic substring would be ‘"aha"’. For the function signature, we will pass a simple string as a parameter. Our program should give us an output that will display the longest palindromic substring of the input string.

Let’s dig deeper into it.

Are you sure you're getting this? Is this statement true or false?

The second half of a palindromic word is the same as the first, but backwards.

Press true if you believe the statement is correct, or false otherwise.

Coming to the main problem, let's find a brute force method to find the longest palindromic substring.

For the brute force method, the logic is that you'll find all substrings. Let's say we have the string "Maham" again. You'd try to generate all substrings in it.

After obtaining all the substrings, what we'll do is reverse each substring, and check whether it's palindromic or not. This way we'll naturally keep the longest palindromic one.

Let's see how we will implement it through code. At first, we will check if our string is of length 1 or not. If it has a length of 1, then we don't have to proceed, as you know that a single character is a palindrome by itself.

Then we can check if our string is of length 2 or not. We are checking these specific lengths to avoid extra work, as our function doesn't have to execute all the awy. Adding these checks will improve the method's performance.

What will happen if we pass the string "Maham"?

Try this exercise. Click the correct answer from the options.

Why will the interpreter skip the previous code snippet for the input string "Maham"?

Click the option that best answers the question.

The length of the input string is less than 2
Our code is not correct
The length of the input string is not equal to 2

Let's move on as we haven't completed our solution yet. Now the problem is that the input string is neither less than 2 nor equal to 2. The only possibility left is that it will be greater than 2. So the question arises, how are we going to deal with such strings?

In this case, we will find all possible substrings with the help of loops. Here i is the starting point of a substring and j is the ending point.

The loops will form the substrings with indices (0, 4), (0, 3), (0, 2), and so on.

The next step is to check if our substring is a palindrome or not. We will check it using the following line of code.

In the following step, if the substring is a palindrome, we will check if it is the longest palindromic substring. For that purpose, we can create an output variable that will store the longest palindromic substring found. Let's then compare our substring with the output string. If it is longer than the output string, we'll update it.

In this way, our loop will iterate through the length of the string and we will find the longest palindromic substring.

If no palindromic substring is found, then output will remain empty and the function will return the first character of the string.

The time complexity for this function will be O(n*3), as the complexity to find all possible strings is O(n*2) and the one to check if it's a palindrome is O(n). This results in O(n2*n)= O(n3).

Is there a better, more efficient method to solve this problem?

Of course! There are many solutions to a problem if we'll look hard enough for them. We will share another solution with you that will use the dynamic programming technique to find the longest palindromic substring.

xxxxxxxxxx
 
def longestPalindromicString(string: str) -> str:
    if len(string) < 2:
        return string
​
    if len(string) == 2:
        if string == string[::-1]:
            return string
        return string[0]
​
    output = ""
    for i in range(len(string)):
        for j in range(len(string) - 1, i, -1):
            if string[i : j + 1] == string[i : j + 1][::-1]:
                if len(output) < len(string[i : j + 1]):
                    output = string[i : j + 1]
​
    if not output:
        return string[1]
​
    return output

In this method, we will create an indexed table (2D array) having n rows and m columns where n and m are equal to the length of the string. You may wonder why we're using such a table.

Well, dynamic programming is about using solving sub-problems of a larger problems, and then using those results to avoid any repeat work. The shape of the two-dimensional array allows us to more intuitively hold solutions of subproblems. This will make more sense as we continue-- the table helps us easily model our findings thus far.

A sample 2-dimensional array syntax is as follows:

PYTHON

1array = [[...], [...], ..., [...]]

Let us revisit the string "maham". We'll create a table having rows and columns equal to the length of the string. This is 5 in our case.

Now we'll show you how to fill this table so that we can find the longest palindromic substring. We will fill the diagonal first because the diagonal indicates a single element (for example, if the starting point is 0 and the ending point is also 0, then what we're operating on is just the substring m). See the diagram below.

The logic is similar to our brute force solution-- we want to find the substring and check if it is a palindrome or not. If it is a palindrome, then fill True in the table at that position. With that said, let's fill up the diagonal.

Now let's operate on all remaining substrings. How will we check if the substring is a palindrome? We will compare the element in the starting position and element in the ending position, and move "in-wards", saving a lot of effort by eliminating unnecessary work.

TEXT

1for start = end, "a" is palindromic,
2for start + 1 = end, "aa" is palindromic (if string[start] = string[end])
3for start + 2 = end, "aba" is palindromic (if string[start] = string[end] and "b" is palindromic)
4for start + 3 = end, "abba" is palindromic (if string[start] = string[end] and "bb" is palindromic)

The big idea is that we won't have to repeatedly check substrings that can't possibly be a palindrome. If both elements are the same, our substring is a palindrome, and we continue the check by moving towards the middle with two pointers. Otherwise, if it's not a palindrome, our "starting point" already verifies that.

But we'll need to build up this table to know. For traversing the table above the diagonal, we can use the following code:

So, the above loops will traverse the area above the diagonal in a bottom-up manner (for example, (3, 4), (2, 3), (2, 4).. and so on). Then we'll see if the substring is a palindrome or not. At the first iteration, the loop will check the (3, 4) substring (i.e start is 3 and the end is 4).

In this case, there will be no value at (3, 4) because the substring is not a palindrome. We will keep checking the substrings and get the longest palindromic substring at the end.

The key to understanding the rest of the implementation is this pseudocode:

TEXT

1for start + distance = end, str[start, end] will be palindromic
2if str[start] == str[end]
3and
4str[start + 1, end - 1] (the "inner" part of the string) is palindromic

What we're doing is moving "inwards" at each step, so we do start + 1 and end - 1. It also means we can use this state transition equation:

TEXT

1state(start, end) is true if:
2for start = end, 
3for start + 1 = end,  if str[start] == str[end]
4for start + 2 <= end, if str[start] == str[end] && state(start + 1, end - 1) is true

The time complexity of this program is O(n^2) as the time complexity for creating the table is O(n*2). For traversing and filling the table it is O(n^2) as well, and thus reduces to an O(n^2) solution.

In this solution, we are creating a table of size n*n. So the space complexity will also be O(n^2).

The maxLen variable keeps track of the longest palindromic substring and output has stored the longest palindromic string found so far. In the end, the function returns the output i.e the longest palindromic substring.

xxxxxxxxxx
 
def longestPalindromicString(string: str) -> str:
    length = len(string)
    table = [[False] * length for _ in range(length)]
    output = ""
​
    for i in range(length):
        table[i][i] = True
        output = string[i]
​
    maxLen = 1
    for start in range(length - 1, -1, -1):
        for end in range(start + 1, length):
            if string[start] == string[end]:
                if end - start == 1 or table[start + 1][end - 1]:
                    table[start][end] = True
                    if maxLen < end - start + 1:
                        maxLen = end - start + 1
                        output = string[start : end + 1]
    return output
​
print(longestPalindromicString('algoog'))

One Pager Cheat Sheet

We need to write a method to find the longest palindromic substring within a given lowercase alphabetical string, with O(n^2) time and space complexity. Where there are multiple longest substrings of the same length, return the first to appear.
I have to find the longest palindromic substring of a given string, which is a palindrome that can be read the same backward and forward.
The key phrase of a palindrome is that the second half is the same as the first half, but reversed.
The brute force method to solve this problem consists of generating all substrings and then reverse each to check for palindromicity, allowing us to keep the longest palindromic one.
We can check the length of our string and get an early exit if it is 1 or 2, and then look for the longest palindromic substring in the rest of the case.
The input string being of length 5 (Maham) means that the code snippet if it has a length of 1 will be skipped and the interpreter will proceed to the next one.
We can find the longest palindromic substring by looping through the input string and comparing the substrings with an output variable to store the longest string found so far.
The time complexity to find the longest palindrome in a string using this approach is O(n^3), but there may be a more efficient method.
We use a 2-dimensional array to store subproblem results and track our progress towards solving the longest palindromic substring problem for a given string with dynamic programming.
We fill the diagonal of a table to determine which substrings are palindromes, as a step prior to finding the longest palindromic substring.
We can use a bottom-up approach and compare the element in the starting position and element in the ending position of substrings to check if they are palindromic and skip over unnecessary work.
By moving "inwards" and using the state(start, end) equation, we get a time complexity of O(n^2) and space complexity of O(n^2), leading to a final output of the longest palindromic substring.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx
}
 
var assert = require('assert');
​
const longestPalindrome = (str) => {
  if (!str || str.length <= 1) {
    return str;
  }
​
  let longest = str.substring(0, 1);
  for (let i = 0; i < str.length; i++) {
    let temp = expand(str, i, i);
    if (temp.length > longest.length) {
      longest = temp;
    }
    temp = expand(str, i, i + 1);
    if (temp.length > longest.length) {
      longest = temp;
    }
  }
  return longest;
};
​
const expand = (str, begin, end) => {
  while (begin >= 0 && end <= str.length - 1 && str[begin] === str[end]) {
    begin--;
    end++;
  }
  return str.substring(begin + 1, end);
};
​
try {
  assert.equal(longestPalindrome(''), '');
​

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.

Constraints

Try to solve this here or in Interactive Mode.

We'll now take you through what you need to know.

Longest Palindromic Substring

Are you sure you're getting this? Is this statement true or false?

Try this exercise. Click the correct answer from the options.

Click the option that best answers the question.

One Pager Cheat Sheet

This is our final solution.

Alright, well done! Try another walk-through.

Programming Categories

Popular Lessons