حل سوال پنجم LeetCode

سلام دوستان عزیز، من مهدی شاملو هستم و برگشتم با یکی از سوالات کلاسیک و خیلی مهم LeetCode: سوال شماره ۵ – Longest Palindromic Substring 😎

این سوال Medium هست، اما یکی از اون سوالاتیه که تقریباً تو همه مصاحبه‌های شرکت‌های بزرگ میاد و حل بهینه‌اش نشون‌دهنده درک خوب از الگوریتمه.

مثل همیشه می‌گم: راه‌های مختلفی برای حل وجود داره، اما من قبلاً یک روش ساده داشتم که بعضی تست‌کیس‌ها رو پاس نمی‌کرد. حالا یک روش خیلی بهتر و بهینه‌تر رو براتون نوشتم که ۱۰۰٪ همه تست‌کیس‌های LeetCode رو پاس می‌کنه. البته خیلی ازم وقت گرفت 😅

صورت سوال: Longest Palindromic Substring

در یک رشته (طول ۱ تا ۱۰۰۰، فقط حروف انگلیسی و اعداد)، باید طولانی‌ترین زیررشته پیوسته (substring) رو پیدا کنیم که پالیندروم باشه. پالیندروم یعنی از جلو و عقب یکسان خونده بشه (مثل "aba" یا "bb").

مثال‌ها:

Input: s = "babad" Output: "bab" (یا "aba" هم درسته – هر دو طول ۳ دارن)

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

از وسط بپر !

اسم این روش رو به از روی حرکت از وسط به طرفین انتخاب کردم . این روش یکی از بهترین برای این سوال هست. ایده‌ام اینه که برای هر موقعیت ممکن در رشته، فرض کنیم اونجا "مرکز" پالیندروم هست و به چپ و راست گسترش بدیم تا جایی که کاراکترها برابر باشن.

پالیندروم دو نوع مرکز داره:

• فرد: یک کاراکتر وسط (مثل "aba")

• زوج: بین دو کاراکتر یکسان (مثل "bb")

پیچیدگی زمانی: O(n²) پیچیدگی فضایی: O(1) → عالی!

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        
        start = 0
        end = 0
        
        def expand_around_center_v2(left: int, right: int):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return left + 1, right - 1
        
        for i in range(len(s)):
            
            # Case 1: Odd length palindrome (center is a single character)
            # Example: "aba" → center at 'b'
            l1, r1 = expand_around_center_v2(i, i)
            
            # Case 2: Even length palindrome (center is between two characters)
            # Example: "bb" → center between the two 'b's
            l2, r2 = expand_around_center_v2(i, i + 1)
            
            if r1 - l1 > end - start:
                start, end = l1, r1
            if r2 - l2 > end - start:
                start, end = l2, r2
                
            print(f"start : {start} and end : {end}")
            print("#" * 100)
        
        return s[start:end + 1]

چرا این روش خوبه؟

• نیازی به ساخت همه زیررشته‌ها نداره

• فضای اضافی مصرف نمی‌کنه

• تو مصاحبه‌ها اگر ازش استفاده کنی خیلی هوشمندانه‌ست

اگر روش دیگه‌ای بلدید حتماً تو کامنت‌ها بگید تا یاد بگیرم و شاید پست جداگونه‌ای براش بسازیم 🚀

سوالی بود بپرسید، خوشحال می‌شم کمک کنم

نویسنده: مهدی شاملو | Mahdi Shamlou