پرش به محتویات

Longest Substring Without Repeating Characters

تاریخ: جلسه ۱ - ۹ مرداد ۱۴۰۳

صورت سوال

لینک سوال: 3. Longest Substring Without Repeating Characters

یک string با نام s به شما داده شده است، طولانی‌ترین زیررشته با کاراکترهای غیرتکراری را در آن بیابید.

دقت کنید که زیر رشته با زیرمجموعه فرق میکند. به مثال‌های زیر توجه کنید:

مثال ۱:

ورودی: s = abcabcbb

خروجی: ۳

توضیح: جواب abc با طول ۳ است.

مثال ۲:

ورودی: s = bbbbb

خروجی: ۱

توضیح: جواب b با طول ۱ است.

مثال ۳:

ورودی: s = pwwkew

خروجی: ۳

توضیح: جواب wke با طول ۳ است.

⚠️ توجه کنید که پاسخ باید یک زیررشته باشد. pwke یک زیرمجموعه (زیردنباله) است و نه یک زیررشته.

قیدهای مسئله:

  • 0 <= s.length <= 5 * 104

  • رشته s شامل حروف انگلیسی، اعداد، علامت‌ها و space است.

منابع حل سوال

What is Sliding Window Algorithm? Examples

پاسخ سوال

این پاسخ از ویدیوی چنل neetcode در یوتیوب برداشته شده است. لینک ویدیو

کد پاسخ:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:

        seen = set()

        left = 0

        max_length = 0

        left_pointer = 0



        for right in range(len(s)):

            while s[right] in seen:

                seen.remove(s[left])

                left += 1

            seen.add(s[right])

            if right - left + 1 > max_length:

                max_length = right - left + 1

                left_pointer = left



        return max_length

توضیحات:

فرض می‌کنیم که با تکنیک sliding window که در بالا اشاره شد آشنا هستید.

دو متغیر right و left را تعریف می‌کنیم تا به تعبیری، اندیس راست و چپ پنجره‌ی متحرک ما باشند. متغیر right در یک حلقه هر بار افزوده می‌شود و left بسته به نیاز تغییر می‌کند.

هر بار یک واحد به سمت راست می‌رویم.

اگر کاراکتری که روی آن هستیم قبلا دیده نشده است، آن را به لیست کاراکترهای دیده شده اضافه می‌کنیم.

اگر طول پنجره از max_length ای که تا الان پیدا کرده‌ایم بیشتر باشد، max_length را با مقدار جدید آپدیت می‌کنیم.

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

اما چرا؟

لیست دیده‌شده‌ها (seen) حاوی کاراکترهای بزرگترین زیررشته‌ای است که تا الان پیدا کرده‌ایم، نه تمام کاراکترهایی که تا الان دیده‌ایم.

فرض کنید رشته‌ی ما

a  b  c  d  e  f  c  h i

8  7  6  5  4  3  2  1  0

دقت کنید که در هرمرحله هدف ما یافتن طولانی ترین زیررشته‌ای است که اولین کاراکتر آن در خانه left است.

فرض کنید الان left خانه ۰ ام است. یعنی آغاز رشته اصلی. خب ما پیش می‌رویم و می‌رویم تا جایی که برای مثال right به ۵ می‌رسد. یعنی تا الان بزرگترین زیررشته‌ای که آغازگر آن ۰ باشد طولش ۶ است (۰ تا ۵ می‌شود ۶ کاراکتر). حالا فرض کنید right یک واحد جلو می‌بریم و ۶ می‌شود. اما میبینم که کاراکتر ۶ ام را قبلا دیده‌ایم، در خانه ۲ ام.

این یعنی چه؟

یعنی اینکه ما اگر از خانه ۰ شروع کنیم، نهایتا به یک زیررشته متوالی با ۶ کاراکتر خواهیم رسید و دیگر بزرگتر از این نمی‌شود. چون هرچقدر هم بزرگترش کنیم، وسطش (خانه ۶ ام) یک کاراکتر غیرتکراری وجود دارد و کار را خراب می‌کند.

پس باید چه کنیم؟ باید قبول کنیم که دیگر کار با ما left ای که ۰ باشد تمام شده و باید به سراغ حالت‌های دیگر برویم. پس ناچارا left را یک واحد به سمت جلو می‌بریم و کاراکتر موجود در خانه ۰ را از لیست دیده شده‌ها حذف می‌کنیم تا ببینیم اگر شروع زیررشته خانه ۱ ام باشد چه اتفاقی می‌افتد. اما یادمان نرود که خانه ۶ یا همان right را در خانه ۲ دیده بودیم، پس یعنی این زیررشته جدید (bcdefc) که از ۱ آغاز می‌شود به ۶ می‌رسد هنوز هم عنصر تکراری (۶ و ۲) دارد.

در واقع اگر از ۱ هم شروع کنیم، نهایتا تا خانه ۵ می‌توانیم جلو برویم چون ۶ امی تکراری می‌سازد. پس وقتی left برابر با ۱ باشد هم چیز خاصی عایدمان نمی‌شود. ناچارا دوباره left را یک واحد افزایش می‌دهیم و کاراکتر موجود در خانه ۱ را از لیست دیده‌شده‌ها حذف می‌کنیم. باز هم تکراری داریم و مجبوریم ۲ را هم از لیست حذف کنیم و left را یک واحد افزایش دهیم. در واقع می‌توان گفت که ما مطمئن هستیم اگر left برابر با ۲ باشد، بهترین زیررشته‌ای که می‌تواند به ما تحویل دهد طولش از چیزهایی که تا الان پیدا کرده‌ایم کمتر است.

بگذریم، حالا left شده ۳ و right هم ۶ است(defc). یعنی ۴ کاراکتر داریم.

اکنون می‌توانیم ۶ را به لیست دیده شده ها اضافه کنیم و مطمئن شویم که اگر از خانه ۳ شروع کنیم، حداقل تا ۶ می‌توانیم پیش برویم بدون آنکه کاراکتر تکراری ببینیم.

حالا right را جلو می‌بریم، آنقدر می‌رویم تا به خانه ۸ ام می‌رسیم و طول زیررشته ۶ می‌شود. مقایسه می‌کنیم که آیا این طولی که الان پیدا کرده‌ایم بزرگتر از بزرگترین طولی است که قبلا پیدا کرده بودیم؟ اگر جواب بله است، max_length را آپدیت می‌کنیم. البته توجه داشته باشید که این مقایسه را هر بار که right افزایش می‌یابد انجام می‌دهیم.