A LeetCode Daily Series — Day 63

Welcome to this exploration of finding the longest palindromic substring in a given string. We’ll start by understanding the problem and then dive into two efficient solutions to solve it.

Longest Palindromic Substring - LeetCode leetcode.com

Can you solve this real interview question? Longest Palindromic Substring

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

A LeetCode Daily Series — Introduction | Ritesh Shakya riteshakya.com.np

Hey everyone, I’m excited to announce that I’m embarking on a journey to conquer LeetCode!

Understanding the Problem

Given a string s, the task is to find the longest palindromic substring in s. A palindromic substring is a substring that reads the same backward as forward.

Example 1:

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

Example 2:

Input: s = "cbbd"
Output: "bb"

Using Efficient Approach (Expand Around Center)

The idea is to expand around the center of the palindrome. A palindrome mirrors around its center, so we can check palindromes from the center outward. This approach takes advantage of this property by considering each index as the center of a potential palindrome.

def longestPalindrome(self, s: str) -> str:
    res = ""
    resLen = 0
    stringLen = len(s)

    for i in range(stringLen):
        # odd length
        l, r = i, i

        while l >= 0 and r < stringLen and s[l] == s[r]:
            if (r - l + 1) > resLen:
                res = s[l : r + 1]
                resLen = r - l + 1

            l -= 1
            r += 1

        # even length
        l, r = i, i + 1
        while l >= 0 and r < stringLen and s[l] == s[r]:
            if (r - l + 1) > resLen:
                res = s[l : r + 1]
                resLen = r - l + 1

            l -= 1
            r += 1

    return res

Explanation

1. Initialization:

   • res stores the longest palindromic substring found so far.
   • resLen stores the length of this substring.
   • stringLen is the length of the input string s.

2. Loop through each character:

   • Treat each character as the center of a palindrome.
   • Check for both odd-length and even-length palindromes.

3. Expand around the center:

   • Use two pointers l and r to expand outwards while the characters at these pointers are equal.
   • Update res and resLen if a longer palindrome is found.

Time Complexity: O(n^2), where n is the length of the string. For each character, we expand around the center, which takes linear time.

Space Complexity: O(1) because we use only a few extra variables.

Using Efficient Approach 2 (Dynamic Programming)

In this approach, we use dynamic programming to build a solution. The idea is to use a 2D array to keep track of palindromic substrings. If s[i:j+1] is a palindrome, then s[i+1:j] must also be a palindrome, and s[i] must equal s[j].

def longestPalindrome(self, s: str) -> str:
    if s[::-1] == s:
        return s

    start, size = 0, 1

    for i in range(1, len(s)):
        l, r = i - size, i + 1

        s1 = s[l-1:r]

        if l >= 1 and s1[::-1] == s1:
            size += 2
            start = l - 1
        else:
            s2 = s[l:r]
            if s2[::-1] == s2:
                size += 1
                start = l

    return s[start:start+size]

Explanation

1. Check for a quick palindrome:

   • If the entire string is a palindrome (i.e., it reads the same forward and backward), return it immediately.

2. Initialization:

   • start and size are initialized to track the starting index and size of the longest palindromic substring found so far. Initially, start is 0 and size is 1 (the smallest palindrome is a single character).

3. Iterate through the string:

   • For each character in the string (starting from the second character), consider two cases for the possible palindrome length: odd and even lengths.
     • Odd-length palindrome: Check the substring s[l-1:r] where l = i - size and r = i + 1.
     • Even-length palindrome: Check the substring s[l:r] where l = i - size and r = i + 1.
   • If the substring is a palindrome, update start and size to reflect the new longest palindrome found.
   • Continue expanding the window size as needed.

Time Complexity: O(n^2), as we check all possible substrings.

Space Complexity: O(1), since we use only a few extra variables without additional data structures.

Conclusion

In this article, we’ve explored the problem of finding the longest palindromic substring in a given string. We discussed two efficient approaches: expanding around the center and a dynamic programming-inspired method.

Each approach has its trade-offs in terms of time and space complexity, and choosing the right approach depends on the constraints of the problem and the size of the input.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series

A LeetCode Daily Series — Day 64 | Ritesh Shakya riteshakya.com.np

Today’s problem is called "Word Break”