برای دسترسی به سوال 3 لیتکد میتونید از این لینک استفاده کنید. سطح این سوال Medium است.
اگر پیشنهادی برای اصلاح پست دارید، میتونید از طریق دکمهی "پیشنهاد اصلاح متن" وارد ریپازیتوری وبلاگ در github بشید و تغییرات مورد نظرتون رو پیشنهاد بدید.
شرایط مسئله
در این مرحله، شرایط خاص مسئله و حالتهای edge case رو بررسی میکنیم. این شرایط باید در توضیحات سوال یا مثالها مشخص شده باشن یا اینکه از پاسخهای پیش فرض استفاده کنیم.
- در این سوال ممکنه substringها متفاوت باشن و مثلا چند substring با طول n و شرایط خواسته شده داشته باشیم، اما مهم، برگرداندن طول substring با شرایط خواسته شده است، حتی اگه چند تا باشن. مثلا در abccabb دو سابسترینگ abc و cab بلندترین substringها با کاراکترهای غیر تکراری هستن، هر دو هم طول 3 دارن، پس 3 رو به عنوان جواب برمیگردونیم.
- آیا substringها باید contiguous باشن؟ بله. ما دنبال substring هستیم، نه subsequence. فرق substring و subsequence چیه؟ مثلا در رشته abcbbd اگه بخوایم یه substring مثال بزنیم میشه سه حرف اولش یعنی abc که contiguous هم هستن. اما اگه بخوایم یه subsequence مثال بزنیم، میشه abcd که شامل سه حرف اول، دو break و حرف آخر است. نکته مهم اینه که این سابیسکوئنس، contiguous نیست.
- آیا کوچک و بزرگ بودن حروف مهمه؟ خیر، فرض بر اینه که stringها فقط حروف کوچک دارن.
نوشتن test case
در این مرحله، چند مثال مینویسیم که هم شرایط خواسته شده و هم edge case هایی که بالاتر اشاره کردیم رو pass کنه.
|
|
راه حل منطقی
در این مرحله به دنبال working solution هستیم، یعنی راه حلی منطقی که بتونه مسئله رو حل کنه. به راه حل بهینه فکر نمیکنیم. درگیر زبان برنامه نویسی و محدودیتهای اون هم نخواهیم بود.
به راه حل brute force که صرفا جواب بده فکر میکنیم و بهینه بودنش برامون مهم نیست. اولین راه حل اینه که همه substringهایی که کاراکتر تکراری ندارن رو دربیاریم و بین اونها، اونی که بیشترین کاراکتر رو داره مشخص کنیم.
اما راه حل بهتری هم هست، کانتری به نام longest با مقدار اولیه 0 تعریف میکنیم. روی string ورودی پیمایش میکنیم و هر بار چک میکنیم که آیا اون کاراکتر رو دیدهایم یا نه؟ اگر ندیده باشیم، به مجموعه کاراکترهای تا الان دیده شده اضافهاش میکنیم و همچنین چک میکنیم که تعداد اعضای مجموعه کاراکترهای تا الان دیده شده چندتاست؟ اگه از عدد longest بیشتر باشه، مقدار longest رو با این مقدار جدید آپدیت میکنیم.
مثلا برای استرینگ abcbdca از کاراکتر اول شروع میکنیم. در مرحله صفر، مجموعه کاراکترهای دیده شده برابر {} و longest = 0 است.
با دیدن کاراکتر اول، چک میکنیم که آیا قبلا اون رو دیدهایم یا نه؟ نه، پس مجموعه کاراکترهای دیده شده برابر {a} و longest = 1 است.
با دیدن کاراکتر دوم، چک میکنیم که آیا قبلا اون رو دیدهایم یا نه؟ نه، پس مجموعه کاراکترهای دیده شده برابر {a,b} و longest = 2 است.
با دیدن کاراکتر سوم، چک میکنیم که آیا قبلا اون رو دیدهایم یا نه؟ نه، پس مجموعه کاراکترهای دیده شده برابر {a,b,c} و longest = 3 است.
با دیدن کاراکتر چهارم که b هست، چک میکنیم که آیا قبلا اون رو دیده ایم یا نه؟ بله. پس دیگه جلو نمیریم. مقدار longestمون برابر 3 میمونه و مجموعه کاراکترهای تا الان دیده شده، پاک میشه. پس حالا مجموعه کاراکترهای تا الان دیده شده {} و longest = 3 است.
حالا از کاراکتر دوم که b است پیمایش رو شروع میکنیم و مثل الگوریتم بالا عمل میکنیم. چک میکنیم که آیا قبلا اون رو دیدهایم یا نه؟ نه، پس مجموعه کاراکترهای دیده شده برابر {b} و longest = 3 است. مقدار longest آپدیت نشد چون تعداد اعضای مجموعه 1 هست و از longest بیشتر نیست.
با همین روش میریم جلو تا به پایان برسیم. در نهایت جواب 4 خواهد بود.
تبدیل راه حل به کد
یه نکته منطقی که همین ابتدا به ذهن میرسه اینه که تعداد کاراکتر استرینگ ورودی رو چک کنیم. اگه 0 بود، جواب ما 0 و اگه 1 بود، جواب ما 1 خواهد بود.
|
|
پیچیدگی زمانی و حافظهای
در این مرحله به بررسی پیچیدگی زمانی و حافظه ای راه حل میپردازیم. یعنی تحلیل میکنیم که بین زمان اجرای الگوریتم و حافظه مصرفی آن، چه رابطه ای با اندازه ورودی الگوریتم وجود دارد.
پیچیدگی زمانی الگوریتم O(n^2) است. حلقه بیرونی n بار اجرا میشود، حلقه درونی به تعداد کمتر اجرا میشود اما به همون دلیلی که در حل سوال 1 بیان شد، مرتبه زمانی، به مرتبه پایینتر نمیرسد و O(n^2) میماند.
پیچیدگی حافظهای O(n) است. چرا؟ چون حداکثر مقدار حافظهای که در طول اجرا به آن نیاز دارد، n است. این مقدار حافظه توسط آبجکت seenChars مصرف میشود. seenChars کاراکترهایی که تاکنون دیده شده است را نگه میدارد و اندازه آن وابسته به تعداد کاراکترهای unique در substring است. در بدترین حالت، زمانی که همهی کاراکترها متمایز باشند، اندازهی seenChars میتواند به اندازه طول string ورودی باشد. پس پیچیدگی حافظهای O(n) است.
بهینهسازی
برای بهینه کردن این الگوریتم، از تکنیک sliding window استفاده میکنیم. این تکنیک مشابه two pointer است اما نیازمندیهای بیشتری برای استفاده داره. ایده اصلی پشت تکنیک پنجره کشویی تبدیل دو حلقه تو در تو به یک حلقه است.
اگر مسئله، بر اساس یک آرایه، لیست یا نوع رشته ای از ساختار داده باشد و مفهوم آن عمدتاً مبتنی بر ایدههایی مانند طولانیترین دنباله یا کوتاهترین دنباله باشد، پنجره کشویی میتواند به بهینه کردن الگوریتم کمک کند. پنجره کشویی شامل یه بخش روی استرینگ یا دنباله است، شامل چند عنصر پشت سر هم است، میتواند جلو و عقب برود و میتواند تعداد عناصر مختلفی داشته باشد.
برای استفاده از این تکنیک، باید boundaryها رو مشخص کنیم، یعنی معلوم بشه که مرزهای پنجره کجاست. کانتر longest مثل قبل وجود خواهد داشت. همچنین از ساختمان داده Dictionary استفاده میکنیم تا علاوه بر کاراکتر دبده شده، indexش رو هم ذخیره کنیم.
فرض میکنیم رشته ورودی abcbdaac باشه.
تا الان کاراکتر a رو ندیدهایم. در پایان مرحله یک، پوینتر چپ روی اولین a، پوینتر راست روی اولین b، مقدار longest برابر 1 و دیکشنری seen برابر {a:0} است.
تا الان کاراکتر b رو ندیدهایم. در پایان مرحله دو، پوینتر چپ روی اولین a، پوینتر راست روی اولین c، مقدار longest برابر 2 و دیکشنری seen برابر {a:0, b:1} است.
تا الان کاراکتر c رو ندیدهایم. در پایان مرحله سه، پوینتر چپ روی اولین a، پوینتر راست روی دومین b، مقدار longest برابر 3 و دیکشنری seen برابر {a:0, b:1, c:2} است.
کاراکتر b رو قبلا دیدهایم. این اولین کاراکتر تکراری است که به اون برخورد کردهایم. بقیه کاراکترها unique هستن. به دلیل رعایت contiguous بودن substring، کاراکترهای قبل از اولین b و همچنین خودِ اولین b نمیتونن جزو substring مورد نظر ما باشن. پس باید پوینتر چپ رو به اولین خانهی بعد از اولین b ببریم. در پایان مرحله چهار، پوینتر چپ روی اولین c، پوینتر راست روی اولین d، مقدار longest برابر 3 و دیکشنری seen برابر {a:0, b:3, c:2} است.
تا الان کاراکتر d رو ندیدهایم. در پایان مرحله پنج، پوینتر چپ روی اولین c، پوینتر راست روی دومین a، مقدار longest برابر 3 و دیکشنری seen برابر {a:0, b:3, c:2, d:4} است.
کاراکتر a رو قبلا دیدهایم. اما برامون مهم نیست، چون الان پنجرهمون شامل cbda است و aای که قبلا دیده بودیمش، خارج از پنجرهمونه. فقط indexش رو در دیکشنری آپدیت میکنیم. در پایان مرحله شش، پوینتر چپ روی اولین c، پوینتر راست روی سومین a، مقدار longest برابر 4 و دیکشنری seen برابر {a:6, b:3, c:2, d:4} است.
کاراکتر a رو قبلا دیدهایم. برامون مهمه چون a قبلی که دیده بودیم، هنوز توی پنجرهمون هست. به دلیل رعایت contiguous بودن substring، کاراکترهای قبل از دومین a و همچنین خودِ اون a نمیتونن جزو substring مورد نظر ما باشن. پس باید پوینتر چپ رو به اولین خانهی بعد از دومین a ببریم. در پایان مرحله هفت، پوینتر چپ روی سومین a، پوینتر راست روی دومین c، مقدار longest برابر 4 و دیکشنری seen برابر {a:6, b:3, c:2, d:4} است.
کاراکتر c رو قبلا دیدهایم. اما برامون مهم نیست، چون الان پنجرهمون شامل ac است و cای که قبلا دیده بودیمش، خارج از پنجرهمونه. فقط indexش رو در دیکشنری آپدیت میکنیم. در پایان مرحله هشت، پوینتر چپ روی سومین a قرار گرفته. پوینتر راست به انتها رسیده و نمیتونه جلوتر بره. مقدار longest برابر 4 و دیکشنری seen برابر {a:6, b:3, c:7, d:4} است. پس جواب نهایی برابر 4 خواهد بود.
پیادهسازی الگوریتم جدید به صورت زیر خواهد بود.
|
|
پیچیدگی زمانی و پیچیدگی حافظهای آن O(n) است.