Longest Palindromic Substring Leetcode Solution

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

Example:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Understand The Problem

The first step in problem-solving is to understand the problem.

When you read the problem statement, you might immediately have ideas on how to solve it. Do not jump to conclusions and do not let your mind fool you. It’s best not to trust your instincts, and instead, you should go through systematic steps of analyzing the problem. Using a system will dramatically reduce the chance of a mistake.

Note: During the interview, make sure to ask questions before you start solving the problem! Interviewers often give a vague problem definition, and you have to fill in the details by asking questions.

Let’s look at the problem statement:

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

There is a lot to unpack in every problem statement. First, let’s look at the question overall and then highlight the key parts:

• We are given a string s.
• We need to find the longest palindromic substring within s.

From this information, we can form a basic idea of how the function will look like:

public class LongestPalindromeSubstring {
    public String longestPalindrome(String s) {
        // Your code here
    }
}

At this point, we have no idea how to solve anything. However, we do know the input, we do know the output, and we have a basic sense of the algorithm. Let’s dive a little more into the details before we try coming up with a solution…

Let’s analyze the input.

• String s:
  • Could the string be empty?
    • Yes.
  • Can we expect the string to contain only ASCII characters?
    • Yes.
  • Could the string contain spaces or special characters?
    • Yes.
  • Could the string contain uppercase and lowercase letters?
    • Yes.

Note: Notice how simple these questions are. Yet they are so crucial. ANY change in the answers can mean the difference between solving the algorithm and getting it wrong.

We now have a basic understanding of the problem. Let’s try to come up with a solution.

Note: There’s always a chance you miss something – even after carefully examining each detail. Don’t worry. It’s natural. However, you should treat every mistake as an opportunity to improve. Why did you make a mistake? Can you improve your problem-solving system to ensure that you don’t make the same mistake again? That’s the whole point of learning: identify weaknesses, improve your system, and repeat. Iterate, iterate, iterate.

Coming Up With The Solution

Each algorithm problem is different. There is no single approach that will help you solve every problem. However, I recommend starting by creating examples and walking through them.

Let’s start by creating examples:

• Example 1
  • s = "babad"
  • Why this example?
    • This input is nice because it’s simple.
    • It tests the scenario where the longest palindromic substring is in the middle of the string.
• Example 2
  • s = "cbbd"
  • Why this example?
    • This input is nice because it’s simple.
    • It tests the scenario where the longest palindromic substring has even length.
• Example 3
  • s = "a"
  • Why this example?
    • This input is nice because it’s simple.
    • It tests the scenario where the string contains only one character.

Note: The number of examples you can go through during the interview will be limited. If you have infinite time, it’s best to try a lot of examples where each examines a specific edge-case. However, you don’t have infinite time in an interview, so you have to strike the balance between speed and accuracy.

As a result of not having a lot of time, let’s pick an example that seems to cover various edge-cases:

• s = "babad"

This example is nice because:

• It’s a simple case with a moderately long string.
• It involves finding the longest palindromic substring within the string.
• The result is a palindromic substring, so we can test the correctness of the algorithm.

Exercise:

With the observations in mind, let’s take the example s = "babad" and start thinking about how we can find the longest palindromic substring within s:

• We need to check every possible substring:
  • We’ll use two pointers to represent the start and end of each substring.
  • We’ll iterate through the string and check every possible substring.
  • We’ll determine whether each substring is a palindrome.
  • We’ll keep track of the longest palindromic substring found so far.

Example Dry Run:

• Let’s say our string is "babad".
• We’ll use two pointers to represent the start and end of each substring.
• At each step, we’ll check whether the substring is a palindrome.
  • At index 0, we’ll check substrings "b", "ba", "bab", "baba", "babad".
    • None of
  these substrings are palindromes.
  • At index 1, we’ll check substrings "a", "ab", "aba", "abad".
    • Substring "aba" is a palindrome.
    • We’ll update the longest palindromic substring found so far to "aba".
  • At index 2, we’ll check substrings "b", "ba", "bad".
    • Substring "bab" is a palindrome.
    • We’ll update the longest palindromic substring found so far to "bab".
  • At index 3, we’ll check substrings "a", "ad".
    • None of these substrings are palindromes.
  • At index 4, we’ll check substring "d".
    • None of these substrings are palindromes.
• The longest palindromic substring is "bab".

From this exercise, we have derived an algorithm:

• Initialize variables to keep track of the start and end indices of the longest palindromic substring found so far.
• Iterate through the string and, at each index, expand around the index to find the longest palindromic substring centered at that index.
• Keep track of the longest palindromic substring found so far.

Here is the algorithm written down:

public class LongestPalindromeSubstring {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Note:This process may sound simplistic to you, but there is a powerful lesson here. You can make a simple observation like “We need to check every possible substring,” and begin by doing the most straightforward thing possible: iterating through the string and checking every possible substring. Then, let the algorithm evolve from there.

If you are familiar with strings and dynamic programming, you can see that the algorithm can be solved in O(N^2). From this information, we can make further observations:

• To do better, we can solve this in:
  • O(N^2) or O(N^3)
  • Not all algorithms fit neatly into these time-complexity buckets, but a lot of them do – especially in interviews. As a result, making this type of analysis is helpful to keep moving toward a solution.

Let’s consider each time-complexity and create more insights:

• O(N^2) algorithm means we need to efficiently find palindromes by expanding around each character.
  • This typically involves dynamic programming or expanding around the center.
  • Additional space complexity might be required if we create a table to store intermediate results.
• O(N^3) algorithm means we might need nested loops or brute-force techniques.
  • This could involve checking every possible substring for palindromes.

Note: Notice how we can utilize prior knowledge of time-complexity, algorithms, and data structures to generate ideas of how to solve the problem. Make sure to study the Terminology!

Let’s use the O(N^2) observation. We have a string and need to find the longest palindromic substring.

When we consider finding the longest palindromic substring in the string:

s: "babad"

The longest palindromic substring is “bab” or “aba”.

We formed a new property for the input: the characters are ordered from small-to-large. Can we somehow exploit this property?

• Let’s begin by repeating what we did above: start at index 0.
  • s[0] + s[1] == "ba"; "ba" != "ad"
  • s[0] + s[2] == "bab"; "bab" == "bab" (Palindrome found)
  • s[0] + s[3] == "baba"; "baba" != "adab"
  • s[0] + s[4] == "babab"; "babab" != "daba"
  • s[0] + s[5] == "babad"; "babad" != "aba"
• While we didn’t find an answer, we did find a pattern:
  • s[0] + s[2] = "bab" is a palindrome.
  • We observed that as we move forward in the string, the length of the substring to check for a palindrome increases.
• Let’s clarify some of the things we are noticing:
  • As we move forward, if we find a palindrome, it’s a potential candidate for the longest palindromic substring.
  • If we start at index 0, we can keep expanding the substring to the right and left until we find the longest palindrome centered at index 0.
  • We only need to compare two substrings to go through the string: one expanding from index 0 towards the end and one expanding from index 0 towards the beginning.

This property allows us to optimize our approach by starting from each character and expanding around it to find the longest palindromic substring centered at that character.

Let’s recap:

1. By understanding the definition of a palindrome, we found a pattern for efficiently finding palindromic substrings.
2. Then, by analyzing the pattern, we realized that we need to use dynamic programming to check for palindromes efficiently.
3. We considered the additional property of characters being ordered from small-to-large and noted its potential impact on optimization.

Note: Leaping to this conclusion is not always straightforward. However, with a lot of practice, and by using the understanding of dynamic programming, you will be able to find these types of insights.

These observations give us an O(N^2) algorithm:

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Algorithm Analysis:

• Time Complexity: The algorithm expands around each character in the string, so the time complexity is O(N^2), where N is the length of the input string.
• Space Complexity: The algorithm uses a constant amount of extra space, so the space complexity is O(1).

Dry Run:

Let’s dry run the algorithm with an example:

s: "babad"

1. Start with the definition of a palindrome: a string that reads the same backward as forward.
2. Consider each character as the center of a potential palindrome and expand around it.
3. Keep track of the longest palindrome found so far.
4. Return the longest palindrome.

Testing / Reflection

During an interview, if you have the time, you want to test your code by walking through it step-by-step. It’s not uncommon to make a silly mistake.

During practice, you want to reflect on how the solving process went by asking various questions:

• What is the time complexity?
  • O(N^2)
• What is the space complexity?
  • O(1)
• What are some interesting observations from this problem?
  • The algorithm efficiently finds the longest palindromic substring using dynamic programming.
  • We need to handle edge cases when the palindrome has odd or even length.
• What are some related problems?
  • There are other variations of this problem like finding all palindromic substrings.

Reflection is a great step that allows us to “chunk” the learnings from the problem by connecting it to existing ideas.

What else can you think of? Send feedback!

P.S. you can try it @ https://leetcode.com/problems/longest-palindromic-substring/