🌟 سوال Longest Substring Without Repeating Characters: راه حل بهینه با تکنیک Sliding Window 🚀

اگر در مصاحبه های کاری شرکتهای بزرگ فناوری شرکت کرده باشید، احتمالاً با سوال "طولانی ترین زیررشته بدون تکرار کاراکتر" (Longest Substring Without Repeating Characters) روبه رو شده اید. این سوال یکی از چالشهای کلاسیک در حوزه الگوریتم ها و ساختمان داده است که در پلتفرمهایی مثل LeetCode و HackerRank هم بسیار محبوب است. در این مقاله، با روش حل بهینه و نکات کلیدی این مسئله آشنا میشوید!

🔍 صورت مسئله: چی میخوایم پیدا کنیم؟

فرض کنید یک رشته (String) داریم، مثلاً "abcabcbb". هدف پیدا کردن طولانیترین زیررشته (Substring) بدون کاراکتر تکراری است.

• مثال ۱: برای "abcabcbb"، جواب 3 است (زیررشته "abc").

• مثال ۲: برای "bbbbb"، جواب 1 است (زیررشته "b").

• مثال ۳: برای "pwwkew"، جواب 3 است (زیررشته "wke").

⚙️ روش حل بهینه: تکنیک Sliding Window (پنجره کشویی) 🪟

این تکنیک با استفاده از دو اشارهگر (Pointer) و یک مجموعه (Set) برای ردیابی کاراکترهای تکراری، مسئله را در زمان O(n) حل میکند.

مراحل حل:

1. اشارهگرهای left و right را تعریف میکنیم که ابتدای رشته (index=0) شروع میشوند.

2. یک مجموعه (seen) برای ذخیره کاراکترهای پنجره فعلی.

3. با حرکت right به جلو، کاراکترها را به مجموعه اضافه میکنیم.

4. اگر کاراکتر تکراری پیدا شد، left را تا جاییکه آن کاراکتر حذف شود، جلو میبریم.

5. در هر مرحله، ماکزیمم طول زیررشته را بهروزرسانی میکنیم.

📝 پیادهسازی کد در پایتون

python

def longest_unique_substring(s: str) -> int:
    seen = set()
    max_length = 0
    left = 0
    
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

توضیح کد:

• seen: کاراکترهای پنجره فعلی را ذخیره میکند.

• اگر کاراکتر s[right] تکراری باشد، left را تا حذف آن کاراکتر افزایش میدهیم.

• max_length: طول ماکزیمم زیررشته بدون تکرار است.

🧪 آزمایش راهحل با مثالها

• مثال "abcabcbb":

  • پنجره از a شروع میشود و تا c گسترش مییابد (طول=3).

  • وقتی a دوباره میآید، left به 1 منتقل میشود و پنجره جدید "bca" شکل میگیرد.

  • خروجی نهایی: 3.

• مثال "pwwkew":

  • پنجره "pw" → سپس left به 2 منتقل میشود و پنجره "wke" شکل میگیرد.

  • خروجی نهایی: 3.

💡 نکات کلیدی برای مصاحبه

• پیچیدگی زمانی: O(n) چون هر کاراکتر حداکثر دو بار پردازش میشود (توسط left و right).

• فضای مصرفی: O(min(n, m)) که m تعداد کاراکترهای منحصربهفرد مجاز است (مثلاً ۱۲۸ برای ASCII).

• حالتهای خاص: رشته خالی (return 0)، همه کاراکترها یکسان (مثل "bbbbb").

🚀 کاربردهای واقعی این الگوریتم

• اعتبارسنجی پسورد: بررسی عدم تکرار کاراکترها در بخشی از رمز.

• تحلیل دادههای متنی: پیدا کردن طولانیترین دنباله منحصربهفرد در لاگها.

• بیوانفورماتیک: تحلیل توالیهای DNA بدون تکرار نوکلئوتیدها.

✅ جمع بندی

حل مسئله Longest Substring Without Repeating Characters با تکنیک Sliding Window یکی از پایهایترین مهارتهای موردنیاز برای مصاحبههای فنی است. با تمرین این الگوریتم و درک عمیق عملکرد اشارهگرها، میتوانید بهراحتی این چالش را پشتسر بگذارید! 💪

اگر سوالی دارید یا نیاز به توضیح بیشتری دارید، در بخش نظرات بپرسید. 😊