Longest Repeating Character Replacement
لديك سلسلة نصية s تتكوّن من أحرف إنجليزية كبيرة، وعدد صحيح k. يمكنك اختيار ما لا يزيد على k مواضع من s وتغيير الحرف في كل موضع إلى أي حرف كبير آخر.
أعِد طول أطول مقطع فرعي، أي سلسلة من الأحرف المتجاورة، يتكوّن من حرف واحد مكرّر بعد إجراء تغييراتك.
الدالة
- sstring
- سلسلة من الأحرف الكبيرة
- kinteger
- أكبر عدد من الأحرف يمكنك تغييره
- تُرجعinteger
- طول أطول سلسلة فرعية من حرف متكرر واحد يمكنك تكوينها
القيود
1 ≤ s.length ≤ 5 × 104sيحتوي على أحرف إنجليزية كبيرة فقط.0 ≤ k ≤ s.length
أمثلة
- المدخلات
- s = "BAAACAB"k = 1
- المخرجات
- 5
- الشرح
- غيّر
CإلىA، وستقرأ الفهارس من 1 إلى 5AAAAA. ستحتاج ستة أحرف إلى تغييرين: تحتوي الفهارس من 0 إلى 5 علىBوC، وتحتوي الفهارس من 1 إلى 6 علىCوآخرB.
- المدخلات
- s = "AABBBAB"k = 2
- المخرجات
- 6
- الشرح
- في
ABBBAB، من الفهرس 1 إلى 6، الحرفانAهما الحرفان الوحيدان اللذان ليساB، لذا فإن تغييرين يعطيانBBBBBB. يحتوي السلسلة كاملةً على ثلاثة أحرفAوأربعة أحرفB، لذا فهي تحتاج إلى ثلاثة تغييرات.
- المدخلات
- s = "WXYZ"k = 0
- المخرجات
- 1
- الشرح
- بما أنه لا يُسمح بإجراء أي تغييرات، فالإجابة هي أطول تتابع موجود بالفعل في السلسلة النصية. يختلف كل حرف عن الحروف المجاورة له، لذا يتكون هذا التتابع من حرف واحد.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
ما الذي يتغير إذا كان بإمكان s أن يحتوي على أي حرف، وليس الأحرف الكبيرة الـ26 فقط؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
بالنسبة إلى مقطع فرعي ثابت واحد، إلى أي حرف ينبغي أن يتحول كل حرف آخر، وكم تغييرًا يتطلب ذلك؟
يكون المقطع الفرعي صالحًا عندما يكون طوله ناقص عدد مرات ظهور الحرف الأكثر شيوعًا فيه أقل من أو يساوي
k. أوجد أطول نافذة تحقق هذه القاعدة بتحريك حدّيها إلى الأمام عبر السلسلة.احتفظ بعدّادات الأحرف الـ26 وأعلى عدّاد
top. أضف حرفًا واحدًا إلى اليمين؛ وإذا احتاجت النافذة الآن إلى أكثر منkتغييرات، فاحذف حرفًا واحدًا من اليسار كي يبقى الطول كما هو. لا تحتاج النافذة أبدًا إلى أن يتناقص طولها، ولا يحتاجtopأبدًا إلى الانخفاض.
الحل
تكلفة سلسلة فرعية واحدة واضحة: طولها ناقص عدد مرات ظهور أكثر أحرفها شيوعًا. الجزء الصعب هو تجنّب دفع تكلفة جميع السلاسل الفرعية البالغ عددها n². تقرأ نافذة منزلقة السلسلة مرة واحدة، وتعتمد النسخة الأفضل على حقيقتين: لا حاجة أبدًا إلى تقليص النافذة، ولا حاجة أبدًا إلى خفض أعلى عدد لمرات ظهور حرف.
تحقّق من كل سلسلة فرعية
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
أصلح مقطعًا فرعيًا واحدًا. إلى أي حرف ينبغي أن يتغيّر؟ إلى الحرف الذي يظهر بالفعل بأكبر عدد من المرات، لأن كل حرف آخر يجب أن يتغيّر. لذا فإن المقطع الفرعي ذي الطول len، الذي يظهر فيه الحرف الأكثر شيوعًا top مرة، يحتاج إلى len - top تغييرات، ويمكن الوصول إليه عندما تكون هذه القيمة أقل من أو تساوي k.
جرّب كل المقاطع الفرعية. لكل بداية، وسّع النهاية حرفًا واحدًا في كل مرة، واحتفظ بعدد مرات ظهور كل حرف، مع زيادة top كلما تقدّمت. عندها يحتاج كل مقطع فرعي جديد إلى تحديث واحد بدلًا من إعادة العدّ من البداية. يجري التحقّق من كل مقطع فرعي، لذا لن يفوتك أطول مقطع يمكن الوصول إليه.
هذه الطريقة بطيئة لأن السلسلة التي طولها n تحتوي على نحو n²/2 من المقاطع الفرعية. عندما تكون n = 5 × 10^4، فهذا يعني 1.25 × 10^9 عملية تحقّق، وهو عدد أكبر بكثير مما يسمح به الحد الزمني.
الخوارزمية
- عيّن
bestإلى 0. - لكل فهرس بداية، أعد تعيين العدّادات الـ26 و
topإلى 0. - حرّك
endمن البداية إلى الفهرس الأخير. أضفs[end]إلى عدّاده، وزِدtopإذا أصبح ذلك العدّ هو الأعلى. - إذا كان
end - start + 1 - top ≤ k، فيمكن الوصول إلى السلسلة الفرعية: خزّن طولها إذا تجاوزbest. - أعِد
best.
def characterReplacement(s, k):
n = len(s)
best = 0
for start in range(n):
count = [0] * 26 # letters in s[start..end]
top = 0 # count of the most common letter there
for end in range(start, n):
c = ord(s[end]) - ord('A')
count[c] += 1
top = max(top, count[c])
# Every letter that is not the most common one must change.
if end - start + 1 - top <= k:
best = max(best, end - start + 1)
return bestنافذة منزلقة واحدة لكل حرف مستهدف
الفكرة
أعِد صياغة السؤال واختر الحرف أولًا. إذا كان التشغيل النهائي كله A، يصبح السؤال: ما أطول سلسلة فرعية تحتوي على k أحرف على الأكثر ليست A؟ هذه مسألة كلاسيكية للنافذة المنزلقة.
حرّك right عبر السلسلة، وعدّ الأحرف داخل النافذة التي ليست الحرف المستهدف. عندما يتجاوز هذا العدد k، حرّك left إلى الأمام حتى يعود العدد إلى k. توسيع النافذة لا يمكن إلا أن يضيف أحرفًا تحتاج إلى تغيير، لذا تظل النافذة التي تتطلب تغييرات كثيرة كذلك عند توسيعها، ولا يحتاج left إلى الرجوع أبدًا. لكل قيمة من right، تكون النافذة التي تحتفظ بها أطول نافذة مستوفية للشروط تنتهي عند ذلك الموضع.
كرّر ذلك للأحرف الـ26 كلها واحتفظ بأفضل طول. تستغرق كل جولة O(n)، لذا فالمجموع 26 مرورًا، أي نحو 1.3 × 10^6 خطوة عندما يكون n = 5 × 10^4. هذا خطي، لكنه يقرأ السلسلة 26 مرة، ولا ينجح إلا لأن مجموعة الأحرف صغيرة.
الخوارزمية
- لكل حرف مستهدف من
AإلىZ، ابدأ نافذة بالقيمتينleft = 0وothers = 0. - حرّك
rightعبر السلسلة النصية. إذا لم يكنs[right]هو الحرف المستهدف، فأضف واحدًا إلىothers. - طالما أن
others > k، حرّكleftإلى الأمام، واطرح واحدًا منothersعندما لا يكون الحرف الذي يغادر هو الحرف المستهدف. - خزّن
right - left + 1إذا كانت قيمته أكبر منbest. - بعد معالجة الأحرف الـ26 كلها، أعد
best.
def characterReplacement(s, k):
best = 0
for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
left = 0
others = 0 # letters in s[left..right] that are not target
for right in range(len(s)):
if s[right] != target:
others += 1
# Too many letters to change: drop letters from the left.
while others > k:
if s[left] != target:
others -= 1
left += 1
best = max(best, right - left + 1)
return bestنافذة لا يتقلّص حجمها أبدًا
الفكرة
تعامل مع كل حرف في نافذة واحدة. احتفظ بعدّاد لكل واحد من الأحرف الـ26 داخلها، وtop، وهو أعلى عدد. تحتاج النافذة إلى length - top تغييرات، لذا تكون صالحة عندما لا يتجاوز ذلك k.
الحقيقة الأولى: لا تحتاج النافذة أبدًا إلى الانكماش. كل ما يهمك هو تجاوز أفضل طول عُثر عليه حتى الآن، لذا عندما تجعل إضافة s[right] النافذة مكلفة أكثر من اللازم، أزِل حرفًا واحدًا من اليسار. تنزلق النافذة خطوة واحدة وتحافظ على طولها. وعندما لا تكون النافذة مكلفة أكثر من اللازم، فإنها تنمو بمقدار واحد. لذلك يكون طولها دائمًا أفضل طول عُثر عليه حتى الآن، وفي النهاية تكون الإجابة هي n - left.
الحقيقة الثانية: لا يحتاج top أبدًا إلى الانخفاض. عندما يغادر حرف من اليسار، اترك top كما هو، لذا قد يكون أعلى من العدد الحقيقي داخل النافذة. وهذا آمن. بعد الانزلاق، يكون طول النافذة تمامًا top + k، لذا يتطلب توسيعها حرفًا يظهر top + 1 مرة داخل النافذة، وعندها يرتفع top معه. قد يجعل top القديم النافذة تنزلق، لكنه لن يجعلها تنمو عن طريق الخطأ أبدًا، والانزلاق لا يؤدي إلى خسارة أي شيء، لأن النافذة الأطول وحدها هي التي يمكنها تحطيم الرقم القياسي.
في BAAACAB مع k = 1، تنمو النافذة حتى تصبح BAAA، ثم تحتاج BAAAC إلى تغييرين، لذا تنزلق لتصبح AAAC. تؤدي إضافة A التالية إلى رفع top إلى 4، فتنمو النافذة لتصبح AAACA بطول 5. يجعلها B الأخيرة تنزلق مرة أخرى، لذا تكون الإجابة 5.
الخوارزمية
- احتفظ بأعداد الأحرف الـ26، واجعل
left = 0وtop = 0. - حرّك
rightعبر السلسلة: أضفs[right]إلى عدده، وزِدtopإذا أصبح ذلك العدد أكبر. - إذا كان
right - left + 1 - top > k، فإن النافذة تحتاج إلى تغييرات كثيرة جدًا: أزلs[left]من الأعداد، وحرّكleftخطوة واحدة. تنزلق النافذة وتحافظ على طولها. - لا تُنقص
topأبدًا عندما يغادر حرفٌ ما. - أعِد طول النافذة النهائي،
n - left.
def characterReplacement(s, k):
count = [0] * 26 # letters inside the window s[left..right]
left = 0
top = 0 # the highest count any letter has reached in a window
for right in range(len(s)):
c = ord(s[right]) - ord('A')
count[c] += 1
top = max(top, count[c])
# Needs more than k changes: slide the window instead of growing it.
if right - left + 1 - top > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
# The window only grew when a longer valid substring was found.
return len(s) - left
أخطاء شائعة وحالات حدّية
الشيفرة الخاصة بالنافذة قصيرة، لذا تأتي معظم الإجابات الخاطئة من صيغة التكلفة أو من اختصار يبدو صحيحًا فقط.
- إضافة
kإلى أطول سلسلة متتابعة. فيAAABمعk = 3، يعطي ذلك 6، وهو أطول من السلسلة. وفيBAAACABمعk = 1، يعطي 4، لكن التغيير الصحيح يقع في الوسط ويصل بين سلسلتين متتابعتين ليكوّن سلسلة من 5. - حساب التغييرات مقارنةً بالحرف الأول في النافذة بدلًا من الحرف الأكثر شيوعًا فيها. تحتاج النافذة
BAAAإلى تغيير واحد، لا ثلاثة. - إرجاع
n - leftمن نسخة يمكن أن تتقلص فيها النافذة. لا يصح هذا الاختصار إلا عندما لا تصبح النافذة أقصر أبدًا، كما في الشيفرة ذات النافذة الواحدة هنا. إذا كانت حلقتك تقلّص النافذة باستخدامwhileوتعيد حساب الحد الأقصى الفعلي، فاحتفظ بمتغير منفصل اسمهbest. - قياس النافذة باستخدام
right - left. كلا الطرفين داخلها، لذا أضف واحدًا. - التعامل مع
k = 0كحالة خاصة. عندما لا تكون هناك تغييرات، تعيد قاعدة النافذة بالفعل أطول سلسلة متتابعة من حرف واحد.
أسئلة شائعة4
ما التعقيد الزمني لمسألة استبدال الأحرف المتكررة الأطول؟
يعمل حل النافذة الواحدة في زمن O(n)، حيث n هو طول s: يزور right كل حرف مرة واحدة، ويتحرك left مرة واحدة على الأكثر في كل خطوة. ويستخدم مساحة إضافية O(1)، تشمل 26 عدّادًا وعددًا قليلًا من الأعداد الصحيحة.
لماذا لا يلزم تحديث التردد الأقصى عند تحريك النافذة؟
النافذة تحاول فقط تحطيم رقمها القياسي. بعد الانزلاق، يكون طولها top + k، لذا فإن النافذة الجيدة الأطول تحتاج إلى ظهور أحد الأحرف أكثر من top مرة، وهذا يرفع قيمة top على أي حال. إذا كانت قيمة top أعلى من اللازم، فإنها تحافظ فقط على طول النافذة؛ ولا تجعلها تتمدد حين لا ينبغي لها ذلك.
ما الفرق بين هذا وبين أطول سلسلة فرعية من دون أحرف مكررة؟
كلاهما يحرّك حدَّي النافذة على السلسلة، لكن قاعدة النافذة الجيدة تختلف. هناك، تكون النافذة جيدة عندما لا يتكرر أي حرف، ويجب تقليصها حتى يزول التكرار. أمّا هنا، فتكون النافذة جيدة عندما يكون طولها ناقصًا عدد مرات ظهور الحرف الأكثر تكرارًا فيها لا يتجاوز k، ما يسمح بتحريك النافذة بطول ثابت بدلًا من تقليصها.
هل يمكن حل هذه المسألة باستخدام البحث الثنائي؟
نعم. إذا كان بالإمكان الوصول إلى سلسلة فرعية بطول L، فيمكن الوصول إلى كل سلسلة أقصر منها داخلها، لذا يمكنك إجراء بحث ثنائي على L. لكل قيمة L، حرّك نافذة ثابتة بهذا الطول، وتحقّق مما إذا كان أي موضع يحتاج إلى k تغييرات على الأكثر. هذه خوارزمية بتعقيد O(n log n)، وهي أبطأ من حل النافذة الواحدة، لكنها إجابة مقبولة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def characterReplacement(s, k):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "BAAACAB" k = 1
المتوقع
5