Solution For Longest Palindromic Substring

Problem Statement:

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

A palindrome is a word, phrase, number, or other sequence of characters that reads the same backward as forward. For example, “madam” is a palindrome.

Example 1:

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

Example 2:

Input: s = “cbbd”
Output: “bb”

Example 3:

Input: s = “a”
Output: “a”

Example 4:

Input: s = “ac”
Output: “a”

Approach:

We can use the approach of expanding around center. We can imagine that for each character in the string, there are possibly 2n – 1 palindromes, where n is the length of the string. For example, given the string “abc”, we can create the following palindromes: “a”, “b”, “c”, “aa”, “bb”, “cc”, “aba”, “abcba”, “bab”, “bcb”. This gives us a brute force approach of checking each substring to see if it is a palindrome and keeping track of the longest one found so far. However, this approach has a time complexity of O(n^3) since we have to check each substring and for each substring, we have to check if it is a palindrome.

To improve this algorithm, we can use the expanding around center approach. We start by considering each character in the string as the center of a potential palindrome and expand outwards from the center. We can do this for both odd and even length palindromes. For example, for string “abcba”, we can consider the center to be “c” and expand outwards to get the palindrome “abcba”. We can also consider “cb” as the center and expand outwards to get the palindrome “bcb”. We keep track of the longest palindrome found so far and return it at the end.

Solution:

class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
if (n == 0) return “”;
string longest = s.substr(0, 1);
for (int i = 0; i < n – 1; i++) {
string p1 = expandAroundCenter(s, i, i);
if (p1.length() > longest.length())
longest = p1;
string p2 = expandAroundCenter(s, i, i + 1);
if (p2.length() > longest.length())
longest = p2;
}
return longest;
}
private:
string expandAroundCenter(string s, int c1, int c2) {
int l = c1, r = c2;
int n = s.length();
while (l >= 0 && r <= n – 1 && s[l] == s[r]) {
l–;
r++;
}
return s.substr(l + 1, r – l – 1);
}
};

Time Complexity:

The time complexity of this algorithm is O(n^2) because we have two nested loops and for each iteration of the outer loop, we expand around center which takes O(n) time.

Space Complexity:

The space complexity of this algorithm is O(1) because we are not using any extra data structures to store information. We are only using constant space to store variables and return values.

Note:

This algorithm can be further optimized by using Manacher’s algorithm which has a time complexity of O(n) and space complexity of O(n). However, the implementation of Manacher’s algorithm is more complex than this expanding around center approach.

Step by Step Implementation For Longest Palindromic Substring

public class Solution {
    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) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

def longestPalindrome(s):
    # Base case
    if len(s) == 0:
        return ""
    
    # Initialize max length and max string
    max_len = 1
    max_str = s[0]
    
    # Iterate through the string
    for i in range(1, len(s)):
        # Check for odd length palindromes
        odd = getPalindrome(s, i-1, i+1)
        if len(odd) > max_len:
            max_len = len(odd)
            max_str = odd
            
        # Check for even length palindromes
        even = getPalindrome(s, i-1, i)
        if len(even) > max_len:
            max_len = len(even)
            max_str = even
            
    return max_str
            
# Helper function to check if a string is a palindrome
def getPalindrome(s, left, right):
    # Iterate while left and right indices are within bounds
    # and the characters at those indices are equal
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
        
    # Return the substring from the original string
    # that is a palindrome
    return s[left+1:right]

var longestPalindrome = function(s) {
    // edge case
    if (s.length === 0) {
        return "";
    }
    
    let longest = s[0];
    
    for (let i = 0; i < s.length; i++) {
        // check for odd length
        for (let j = 0; i - j >= 0 && i + j < s.length; j++) {
            if (s[i-j] !== s[i+j]) {
                break;
            }
            if (j * 2 + 1 > longest.length) {
                longest = s.slice(i-j, i+j+1);
            }
        }
        // check for even length
        for (let j = 0; i - j >= 0 && i + j + 1 < s.length; j++) {
            if (s[i-j] !== s[i+j+1]) {
                break;
            }
            if (j * 2 + 2 > longest.length) {
                longest = s.slice(i-j, i+j+2);
            }
        }
    }
    
    return longest;
};

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        int maxlen = 1;
        int start = 0;
        bool table[1000][1000] = {false};
        for (int i = 0; i < n; ++i)
            table[i][i] = true;
        for (int i = 0; i < n-1; ++i) {
            if (s[i] == s[i+1]) {
                table[i][i+1] = true;
                start = i;
                maxlen = 2;
            }
        }
        for (int k = 3; k <= n; ++k) {
            for (int i = 0; i < n-k+1 ; ++i) {
                int j = i + k - 1;
                if (table[i+1][j-1] && s[i] == s[j]) {
                    table[i][j] = true;
                    if (k > maxlen) {
                        start = i;
                        maxlen = k;
                    }
                }
            }
        }
        return s.substr(start, maxlen);
    }
};

using System; 

public class Solution {
    public string LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s))
        {
            return "";
        }
        
        int start = 0, end = 0;
        for (int i = 0; i < s.Length; i++)
        {
            int len1 = ExpandFromMiddle(s, i, i);
            int len2 = ExpandFromMiddle(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 - start + 1);
    }
    
    private int ExpandFromMiddle(string s, int left, int right)
    {
        if (left > right)
        {
            return 0;
        }
        
        while (left >= 0 && right < s.Length && s[left] == s[right])
        {
            left--;
            right++;
        }
        
        return right - left - 1;
    }
}