Leetcode 5 - Longest Palindromic Substring | দ্বারা Aditya Dedhia

1 week,4 days ago - macroblocks · 0 মিনিট পড়ার সময়

LeetCode 5 - Longest Palindromic Substring

Topics: 💻 cs🏷️ problem📚 leetcode📄 medium

LeetCode Link: longest palindromic substring writeup

Intuition

Instead of checking if every substring is a palindrome (which requires checking each character), we can observe that palindromes expand symmetrically from their center. For any palindrome, if we start from the middle and expand outward, the characters on both sides will match.

Approach

1. For each possible center position in the string, expand outward while characters match

2. Track the longest palindrome found during all expansions

3. Handle both odd-length palindromes (single character center) and even-length palindromes (two character center) by expanding from each position twice

4. Return the substring corresponding to the longest palindrome discovered

Complexity

Time complexity: O(n2) - we check 2n-1 centers, and each expansion can take up to O(n) time in the worst case (e.g., a string of all same characters)

Space complexity: O(1) - we only store indices and the result substring, no additional data structures needed

Solution

1. Brute Force O(n³)

class Solution:

def longestPalindrome(self, s: str) → str:

if len(s) < 2 or len(set(s)) == 1: # 1 or fewer is always a palindrome

return s

max_palindrome_len: int = 0

max_palindrome_substring: str = ""

len_s: int = len(s)

def is_palindrome(string_to_test: str) → bool: # abc

len_string = len(string_to_test)

for i in range(len_string // 2):

if string_to_test[i] ≠ string_to_test[len_string - i - 1]:

return False

return True

for i in range(len_s):

starting_char_in_s: str = s[i]

for j in range(i, len_s):

substring_to_test: str = s[i:j+1]

substring_to_test_len = len(substring_to_test)

if substring_to_test_len > max_palindrome_len:

if is_palindrome(substring_to_test):

max_palindrome_len = substring_to_test_len

max_palindrome_substring = substring_to_test

return max_palindrome_substring

2. Optimised O(n²)

class Solution:

def longestPalindrome(self, s: str) → str:

len_s: int = len(s)

if len_s < 2 or len(set(s)) == 1:

return s

def expand_palindrome(i: int) → str:

previous_index: int = i - 1

next_index: int = i + 1

while previous_index ≥ 0 and next_index ≤ len_s - 1:

previous_char: str = s[previous_index]

next_char: str = s[next_index]

if previous_char == next_char:

previous_index -= 1

next_index += 1

else:

break

max_odd_palindrome: str = s[previous_index + 1:next_index]

current_index: int = i

next_index: int = i + 1

while current_index ≥ 0 and next_index ≤ len_s - 1:

current_char: str = s[current_index]

next_char: str = s[next_index]

if current_char == next_char:

current_index -= 1

next_index += 1

else:

break

max_even_palindrome: str = s[current_index + 1: next_index]

if len(max_odd_palindrome) > len(max_even_palindrome):

return max_odd_palindrome

return max_even_palindrome

max_palindrome_len: int = 0

max_palindrome_string: str = ""

for index_to_test in range(len_s): # 0(n)

max_palindrome_at_index: str = expand_palindrome(index_to_test) # O(n)

len_max_palindrome_at_index: int = len(max_palindrome_at_index)

if len_max_palindrome_at_index > max_palindrome_len:

max_palindrome_len = len_max_palindrome_at_index

max_palindrome_string = max_palindrome_at_index

return max_palindrome_string

ব্লকসমূহ

থ্রেড আলোচনা