Longest Palindromic Substring

                                            
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int n = s.length();
        if (n == 1) return s;

        int start = 0, len = 1; // variables to track the start and max length of the palindrome found

        vector<vector<bool>> dp(n, vector<bool>(n, false)); // DP table
        for (int i = 0; i < n; i++)
            dp[i][i] = true; // All single characters are palindromes

        // Check for sub-string of length 2
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                start = i;
                len = 2;
            }
        }

        // Check for lengths greater than 2
        for (int k = 3; k <= n; k++) { // sub-string length
            for (int i = 0; i < n - k + 1; i++) { // start index
                int j = i + k - 1; // end index
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    len = k;
                }
            }
        }

        return s.substr(start, len);
    }
};

                                            
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) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

                                            
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) == 0:
            return ""
        max_len = 0
        start = 0
        
        for i in range(len(s)):
            len1 = self.expandAroundCenter(s, i, i)
            len2 = self.expandAroundCenter(s, i, i + 1)
            max_len_here = max(len1, len2)
            if max_len_here > max_len:
                max_len = max_len_here
                start = i - (max_len_here - 1) // 2
                
        return s[start:start + max_len]

    def expandAroundCenter(self, s, left, right):
        L, R = left, right
        while L >= 0 and R < len(s) and s[L] == s[R]:
            L -= 1
            R += 1
        return R - L - 1

                                            
char* longestPalindrome(char* s) {
    int start = 0, end = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = len1 > len2 ? len1 : len2;
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    int size = end - start + 1;
    char* result = (char*)malloc(sizeof(char) * (size + 1));
    strncpy(result, s + start, size);
    result[size] = '\0';
    return result;
}

int expandAroundCenter(char* s, int left, int right) {
    while (left >= 0 && s[right] != '\0' && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

                                            
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 - start + 1);
    }

    private int ExpandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

                                            
var longestPalindrome = function(s) {
    if (!s || s.length <= 1) {
        return s;
    }

    let longest = '';

    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            if (right - left + 1 > longest.length) {
                longest = s.substring(left, right + 1);
            }
            left--;
            right++;
        }
    }

    for (let i = 0; i < s.length; i++) {
        expandAroundCenter(i, i);       // Odd length palindromes
        expandAroundCenter(i, i + 1);   // Even length palindromes
    }

    return longest;
};

                                            
function longestPalindrome(s: string): string {
    if (s.length < 1) return "";

    let start = 0, end = 0;

    const expandAroundCenter = (left: number, right: number) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    };

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

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

                                            
class Solution {
    function longestPalindrome($s) {
        $n = strlen($s);
        if ($n < 2) return $s;
        
        $start = 0;
        $maxLen = 1;
        
        for ($i = 0; $i < $n; $i++) {
            if ($n - $i <= $maxLen / 2) break;
            
            $left = $right = $i;
            while ($right < $n - 1 && $s[$right] == $s[$right + 1]) $right++;
            $i = $right++;
            
            while ($left > 0 && $right < $n && $s[$left - 1] == $s[$right]) {
                $left--;
                $right++;
            }
            
            $newLength = $right - $left;
            if ($newLength > $maxLen) {
                $start = $left;
                $maxLen = $newLength;
            }
        }
        
        return substr($s, $start, $maxLen);
    }
}

                                            
class Solution {
    fun longestPalindrome(s: String): String {
        if (s.isEmpty() || s.length < 2) {
            return s
        }
        
        var start = 0
        var end = 0
        
        for (i in 0 until s.length) {
            val len1 = expandAroundCenter(s, i, i)
            val len2 = expandAroundCenter(s, i, i + 1)
            val len = maxOf(len1, len2)
            if (len > end - start) {
                start = i - (len - 1) / 2
                end = i + len / 2
            }
        }
        
        return s.substring(start, end + 1)
    }
    
    private fun expandAroundCenter(s: String, left: Int, right: Int): Int {
        var l = left
        var r = right
        while (l >= 0 && r < s.length && s[l] == s[r]) {
            l--
            r++
        }
        return r - l - 1
    }
}

                                            
class Solution {
  String longestPalindrome(String s) {
    if (s.isEmpty) {
      return '';
    }
    
    String result = '';
    
    for (int i = 0; i < s.length; i++) {
      String palindrome1 = expandAroundCenter(s, i, i);
      String palindrome2 = expandAroundCenter(s, i, i + 1);
      
      if (palindrome1.length > result.length) {
        result = palindrome1;
      }
      
      if (palindrome2.length > result.length) {
        result = palindrome2;
      }
    }
    
    return result;
  }
  
  String expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length && s[left] == s[right]) {
      left--;
      right++;
    }
    
    return s.substring(left + 1, right);
  }
}

                                            
func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }
    
    var start, end int
    for i := 0; i < len(s); i++ {
        len1 := expandAroundCenter(s, i, i)
        len2 := expandAroundCenter(s, i, i+1)
        maxLen := max(len1, len2)
        if maxLen > end-start {
            start = i - (maxLen-1)/2
            end = i + maxLen/2
        }
    }
    
    return s[start : end+1]
}

func expandAroundCenter(s string, left, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
def longest_palindrome(s)
    return s if s.length <= 1
    
    longest = ""
    
    (0...s.length).each do |i|
        # For odd length palindromes
        len1 = expand_around_center(s, i, i)
        if len1.length > longest.length
            longest = len1
        end
        
        # For even length palindromes
        len2 = expand_around_center(s, i, i + 1)
        if len2.length > longest.length
            longest = len2
        end
    end
    
    return longest
end

def expand_around_center(s, left, right)
    while left >= 0 && right < s.length && s[left] == s[right]
        left -= 1
        right += 1
    end
    
    return s[left + 1..right - 1]
end

                                            
object Solution {
    def longestPalindrome(s: String): String = {
        if (s == null || s.length < 1) return ""

        var start = 0
        var end = 0

        for (i <- 0 until s.length) {
            val len1 = expandAroundCenter(s, i, i)
            val len2 = expandAroundCenter(s, i, i + 1)
            val len = math.max(len1, len2)

            if (len > end - start) {
                start = i - (len - 1) / 2
                end = i + len / 2
            }
        }

        s.substring(start, end + 1)
    }

    def expandAroundCenter(s: String, left: Int, right: Int): Int = {
        var L = left
        var R = right

        while (L >= 0 && R < s.length && s.charAt(L) == s.charAt(R)) {
            L -= 1
            R += 1
        }

        R - L - 1
    }
}

                                            
impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let mut start = 0;
        let mut end = 0;
        
        for i in 0..s.len() {
            let len1 = Self::expand_around_center(&s, i, i);
            let len2 = Self::expand_around_center(&s, i, i + 1);
            let max_len = std::cmp::max(len1, len2);
            
            if max_len > end - start {
                start = i - (max_len - 1) / 2;
                end = i + max_len / 2;
            }
        }
        
        s[start..=end].to_string()
    }
    
    fn expand_around_center(s: &String, left: usize, right: usize) -> usize {
        let mut l = left as i32;
        let mut r = right as i32;
        
        while l >= 0 && r < s.len() as i32 && s.as_bytes()[l as usize] == s.as_bytes()[r as usize] {
            l -= 1;
            r += 1;
        }
        
        (r - l - 1) as usize
    }
}

To solve this coding challenge, we need to find the longest palindromic substring within a given string

s

. A palindromic substring reads the same forward and backward. Several methods can be used to approach this problem, but a common and efficient one involves expanding around the center of potential palindromes.

Explanation

Overview

The problem requires identifying the longest substring which reads the same from both ends. For instance, in the string "babad", both "bab" and "aba" are valid answers, and in "cbbd", "bb" is a valid answer. To solve this efficiently, we will use the "expand-around-center" technique.

Detailed Steps

Initialization : Check the edge case where the input string
s

is empty, returning an empty string immediately if true. Initialize variables to track the maximum length of palindromic substring found (
max_len

) and its starting index (
start

).
Iterate Over the String : Loop through each character in the string, treating each character and each gap between characters as potential centers to expand around.
Expand Around Centers : For each character position in the string, we will expand around two possible centers:

A single character as the center (
expandAroundCenter(s, i, i)

)
A pair of consecutive characters as the center (
expandAroundCenter(s, i, i + 1)

)

Update Maximum Length : For each of these expansions, calculate the length of the palindromic substring. If this length is greater than the previously recorded maximum length, update the maximum length and the starting index of this substring.
Return Result : After processing all characters, return the substring from the starting index
start

with length
max_len

.

Detailed Steps in Pseudocode

Below is the detailed pseudocode complete with comments:

                                            
# Function to find longest palindromic substring
function longestPalindrome(s):
# Edge case: If string is empty, return an empty string
if length of s is 0:
return ""

# Initialize variables to track maximum length and starting index of the longest palindromic substring
max_length = 0
start_index = 0

# Iterate through each character in the string
for each index i in the range from 0 to length of s - 1:
# Expand around the center at a single character
length1 = expandAroundCenter(s, i, i)

# Expand around the center at a gap between two characters
length2 = expandAroundCenter(s, i, i + 1)

# Determine the maximum length from the two possible expansions
max_length_here = max(length1, length2)

# If the current maximum length is greater than the previously recorded maximum length
if max_length_here > max_length:
max_length = max_length_here
# Update the starting index for this substring
start_index = i - (max_length_here - 1) // 2

# Return the longest palindromic substring found
return substring of s from start_index to start_index + max_length

# Helper function to expand around the center and find the length of the palindromic substring
function expandAroundCenter(s, left, right):
# Copy left and right pointers
L = left
R = right

# Expand outwards as long as the characters at L and R are equal and within bounds
while L >= 0 and R < length of s and s[L] is equal to s[R]:
# Move left pointer to the left
L -= 1
# Move right pointer to the right
R += 1

# Return the length of the palindromic substring found
return R - L - 1

Step-by-Step Explanation

Initialization :

If the input string
s

is empty, return an empty string to handle the edge case.
Set
max_length

to 0 to track the length of the longest palindromic substring found.
Set
start_index

to 0 to track the starting index of this substring.

Iteration :

Loop through each index
i

of the string
s

.
For every position, check palindromes centered at
s[i]

(
expandAroundCenter(s, i, i)

) and between
s[i]

and
s[i+1]

(
expandAroundCenter(s, i, i + 1)

).

Expand Around Center :

expandAroundCenter(s, left, right)

checks equality of characters at positions
L

and
R

, expanding outward until they differ or bounds are exceeded.
The length of this palindrome is
R - L - 1

.

Update Maximum Length :

Use
max_length_here

to compare current palindrome lengths (
length1

and
length2

).
Update
max_length

and
start_index

if current palindrome is the longest found.

Return Result :

Extract the substring from
start_index

to
start_index + max_length

and return it.

This approach ensures we efficiently find the longest palindromic substring by considering all possible centers and expanding around them without unnecessary computations.