هفته پیش یکی از سوالات روزانه لیت کد سوالی بود با عنوان Number of wonderful substrings. اگر با این سوال آشنایی ندارین حتما یک بار سوال و مثال هاش رو بخونید و بعد برگردید. من درباره این سوال توضیح های متنوعی خوندم اما اون طور که باید نتونستم با هیچ کدوم ارتباط بگیرم و بگم آهان! کاملا قابل فهمه. برای همین خودم سعی کردم به جواب برسم و با زبان خودم توضیح بدم.
این سوال در واقع مثل یک راه حل brute force قرار نیست تمام حالات ممکن رو ایجاد کنه و بعد از بین اونها انتخاب کنه یا حتی بهینه تر فکر کنه و صرفا حرص بیشتری انجام بده. درباره این سوال کلا باید شکل دیگری فکر کرد. چرا؟چون طول رشته میتونه حداکثر ده به توان پنج باشه پس حتما باید به فکر یه راه حل خطی یا نزدیک به خطی باشیم.
سوال از ما میخواد تعداد زیر رشته هایی که حداکثر یک تکرار فرد رو دارند رو پیدا کنیم. در قدم اول خود این یعنی مسئله در دو قسمت باید حل شه.
· رشته ای بدون تکرار فرد. یعنی همه کارکترها فقط زوج بار تکرار شده باشند مثل “aabb”
· رشته ای فقط با یک تکرار فرد. یعنی فقط یک کاراکتر اجازه داره فرد بار تکرار شه. مثل “aba”
وقتی میخوایم مثال بزنیم فرقی نداره هر مثالی میشه زد و فقط زوجیت و فرد بودن تکرارها حائز اهمیته. مثلا چه بگیم “abaaabb” چه بگیم “aba” در هر دو٬ حرف a زوج بار تکرار شده و حرف b فرد بار تکرار شده. پس وقتی هم بخوایم بفهمیم تا یک پوزیشن مشخص از رشته چه زیررشته هایی میشه ساخت کافیه بفهمیم با چه پترنی رو به رو هستیم. در ادامه بیشتر این بخش توضیح داده میشه.
تا همین قسمت یک نکته جالب وجود داره. ما با یک مشخصه مثل زوج یا فرد سر کار داریم. هر عددی یا زوجه یا فرد پس به سادگی میتونیم نگاه بیتی بهش داشته باشیم و بگیم زوج بار تکرار رو صفر در نظر میگیریم و فرد بار تکرار رو یک. چرا؟ چون اگه مثلا اگر یک رشته خالی داشته باشیم و بخوایم اون رو به صورت بیتی نشون بدیم صفر کافیه چون صفر بار تکرار زوجه. چرا حالت پایه رو رشته خالی در نظر گرفتیم؟ چون همیشه برای حالت پایه آسون ترین حالت رو در نظر میگیریم.
یه ویژگی خوب دیگه در این سوال اینه که گفته حروف a تا j در هر رشته وجود دارند. یعنی در کل به ده تا پوزیشن مختلف نیاز داریم. میتونیم بگیم ده تا بیت. بیت اول رو برای a در نظر میگیریم٬ بیت دوم برای b و به همین ترتیب.
مثال: اگر بخوایم تعداد تکرار حروف در رشته “abaecebb” رو به این روش نشون بدیم باید بگیم:
e d c b a
2 0 1 3 2
0 0 1 1 0
بقیه کاراکترهایی که وجود ندارند هم صفر هستند. در قدم اول همه بیت ها صفر هستند و ما به هر حرفی که برسیم میتونیم بیتش رو برعکس کنیم.
حالا یک نکته وجود داره جالب تر از همه نکات قبلی! اینکه ما میتونیم برای حالت ها الگو پیدا کنیم. دوتا حالت برای ما مطلوبه:
۱) همه کاراکترها زوج تکرار ۲) فقط یکی از کاراکترها فرد تکرار
قبول دارین که اگر در یک رشته همه کاراکترها زوج بار تکرار شن بیت متناظر همه شون صفر میشه؟ اگر قبول ندارین هم اشکالی نداره میتونین یه مثال برای خودتون روی کاغذ بزنین. به ویژگی xor هم نیاز داریم. اگر شما هر چیزی رو با صفر xor کنید به زیبایی همون بیت اولی رو مشاهده میکنین. پس اگر مثلا تا یک ایندکسی به پترن 010 رسیدم و در یک ایندکسی بعد از این هم به پترن 010 رسیدم یعنی این بین یک بخش تماما زوج تکرار داشتم که خوشحالم میکنه و بخشی از جوابه. به تصویر دقت کنید:
به بیان بهتر٬ اگر من یک الگوی تکراری ببینم پس بخشی از جواب رو پیدا کردم. در نتیجه هر پترنی رو ببینم ذخیره میکنم.
شاید اگر به همین روش فکر کردن ادامه بدیم بتونیم بقیه جواب رو هم به دست بیاریم. شرایط بعدی رشته ای که میتونه جواب باشه چیه؟ فقط یک کاراکتر فرد بار تکرار شه. واقعا عالیه پس کافیه دوتا الگو در یک بیت متفاوت باشند. برای اینکه بهتر منظورم رو متوجه شین لطفا به تصویر زیر دقت کنید:
برای اینکه بهتر بتونین باهاش ارتباط برقرار کنید لطفا از قلم و کاغذ استفاده کنید تا خودتون با چندتا مثال تجربه کنید واقعا این حالت ها برقراره.
پس این الگو هم که ببینیم پترنی که در یک ایندکس ایجاد شده با چندتا از پترن های قبلی در یک بیت تفاوت داره٬ به درد میخوره.
حالا تا حدی با ایده آشنا شدیم بیاین برای یک مثال دست به تریس شیم و ادامه بدیم. سعی کنید از روی تریس کدش رو بزنید.
در هر مرحله منظور از mask همون الگویی هست که در هر مرحله از iteration بهش میرسیم. همونطور که بالاتر توضیح دادم الگوهایی که می بینیم رو لازم داریم و به همین دلیل اونها رو در یک map یا آرایه ذخیره میکنیم. متغیر ans هم مشخصا مقدار جواب هست که اگر شرایطی که توضیح دادم پیش بیاد آپدیت میشه.
مثال رو برای رشته aabb شروع میکنیم. توجه کنید در هر مرحله اول چک میکنیم اگر این الگو رو قبلا دیدیم پس پترن همه تکرار زوج وجود داره. در ادامه چک میکنیم آیا قبلا الگویی دیدیم که فقط یک حرف فرد بار تکرار شده باشه؟
لطفا بعد از اینکه خودتون سعی کردین به کد زیر هم نگاهی بندازین.
https://gist.github.com/NasimNajand/592eb6858ffaa89a2df1df93308b29c3
هر سوالی داشتین حتما تو کامنت ها بپرسین.
