Longest Repeating Character Replacement
لديك سلسلة نصية s من أحرف إنجليزية كبيرة، وعدد صحيح k. يمكنك اختيار ما لا يزيد على k مواضع في s وتغيير الحرف في كل موضع منها إلى أي حرف كبير آخر.
أعِد طول أطول سلسلة فرعية، أي مجموعة من الأحرف المتجاورة، تحتوي على حرف واحد متكرر بعد إجراء التغييرات.
الدالة
- sstring
- سلسلة من الأحرف الكبيرة
- kinteger
- أكبر عدد من الأحرف التي يمكنك تغييرها
- تُرجعinteger
- طول أطول سلسلة فرعية من حرف متكرر واحد يمكنك تكوينها
القيود
1 ≤ s.length ≤ 5 × 104- يحتوي
sعلى أحرف إنجليزية كبيرة فقط. 0 ≤ k ≤ s.length
أمثلة
- المدخلات
- s = "BAAACAB"k = 1
- المخرجات
- 5
- الشرح
- يؤدي تغيير
CإلىAإلى جعل الفهارس من 1 إلى 5 تقرأAAAAA. تحتوي نافذتا الأحرف الستة كلتاهما علىBوC، لذا تحتاجان إلى تغييرين.
- المدخلات
- s = "AABBBAB"k = 2
- المخرجات
- 6
- الشرح
- تحتوي الفهارس من 1 إلى 6 على
ABBBAB، ويؤدي تغيير حرفَيAإلى الحصول علىBBBBBB. تحتوي السلسلة بأكملها على أربعة أحرفBفقط من أصل سبعة، لذا تحتاج إلى ثلاثة تغييرات.
- المدخلات
- s = "WXYZ"k = 0
- المخرجات
- 1
- الشرح
- بما أنه لا يُسمح بإجراء أي تغييرات، فالإجابة هي أطول سلسلة موجودة بالفعل في السلسلة النصية. يختلف كل حرف عن الحروف المجاورة له، لذا تتكون تلك السلسلة من حرف واحد.
سؤال إضافي
ما الذي يتغير إذا كان بإمكان s أن يحتوي على أي حرف بدلًا من الأحرف الكبيرة الـ 26؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
بالنسبة إلى مقطع فرعي ثابت، إلى أي حرف ينبغي أن يتحول كل حرف آخر، وكم تغييرًا يتطلب ذلك؟
يكون المقطع الفرعي صالحًا عندما يكون طوله ناقص عدد مرات ظهور حرفه الأكثر شيوعًا أقل من أو يساوي
k. أوجد أطول نافذة تحقق هذه القاعدة بتحريك حدّيها إلى الأمام عبر السلسلة.احتفظ بـ 26 عدّادًا وبأعلى قيمة للعدّ
top. أضف حرفًا واحدًا من اليمين؛ وإذا احتاجت النافذة الآن إلى أكثر منkتغييرات، فاحذف حرفًا واحدًا من اليسار ليبقى الطول كما هو. لا تحتاج النافذة أبدًا إلى أن تتقلص، ولا تحتاجtopأبدًا إلى أن تنخفض.
الحل
احتفظ بالحرف الأكثر شيوعًا في سلسلة فرعية وغيّر بقية الأحرف: تحتاج سلسلة فرعية طولها len ويظهر فيها الحرف الأكثر تكرارًا top مرة إلى len - top من التغييرات. تعثر نافذة منزلقة على أطول سلسلة فرعية تحقق len - top ≤ k في مرور واحد، لأن النافذة لا تحتاج أبدًا إلى الانكماش، ولأن top لا يحتاج أبدًا إلى الانخفاض.
تحقّق من كل سلسلة فرعية
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
لكل بداية، وسّع النهاية حرفًا واحدًا في كل مرة، وحدّث عدد مرات ظهور كل حرف وtop، واختبر len - top ≤ k. تتطلب كل سلسلة فرعية جديدة تحديثًا واحدًا بدلًا من إعادة العد من البداية، ويجري فحص كل سلسلة فرعية، لذا لا يمكن تفويت أطول سلسلة يمكن الوصول إليها.
للسلسلة ذات الطول n نحو n²/2 سلسلة فرعية: 1.25 × 10^9 عملية فحص عندما يكون n = 5 × 10^4.
الخوارزمية
- اضبط
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 واحتفظ بالأفضل: 26 مرورًا خطيًا على ما يصل إلى 5 × 10^4 حرف. وتبقى O(n) فقط لأن الأبجدية صغيرة.
الخوارزمية
- لكل حرف مستهدف من
AإلىZ، ابدأ نافذةً بـleft = 0وothers = 0. - حرّك
rightعبر السلسلة. إذا لم يكنs[right]هو الحرف المستهدف، فأضف واحدًا إلىothers. - ما دام
others > k، حرّكleftإلى الأمام، وأنقص واحدًا عندما لا يكون الحرف الذي يغادر هو الحرف المستهدف. - خزّن
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، وهو أكبر عدّاد. عندما تؤدي إضافة s[right] إلى جعل النافذة باهظة جدًا، احذف حرفًا من اليسار: تنزلق النافذة وتحافظ على طولها، لأن النافذة الأطول وحدها يمكنها تحطيم الرقم القياسي. وإلا فسيزداد طولها بمقدار واحد. طولها دائمًا هو الأفضل حتى الآن، لذا تكون الإجابة n - left.
عندما يغادر حرف، اترك top كما هو، حتى لو أصبح الآن أكبر من العدد الحقيقي. بعد الانزلاق، يصبح الطول مساويًا تمامًا لـ top + k، لذا يتطلب النمو ظهور أحد الحروف top + 1 مرة، وعندها يرتفع top معه. لا يمكن لـ top القديم إلا أن يجعل النافذة تنزلق، والانزلاق لا يمكن أن يُفقدها الرقم القياسي.
في BAAACAB مع k = 1، يتطلب BAAAC تغييرين، فتنزلق النافذة إلى AAAC. يرفع الحرف A التالي top إلى 4، وتنمو النافذة إلى AAACA، بطول 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، لكن تغييرCيدمج تتابعين ليصبح طولهما 5. - حساب التغييرات مقارنةً بالحرف الأول في النافذة بدلًا من الحرف الأكثر شيوعًا فيها. يحتاج
BAAAإلى تغيير واحد، لا ثلاثة. - إرجاع
n - leftمن حلقة تُقلّص النافذة باستخدامwhileوتعيد حساب الحد الأقصى الفعلي. تصبح هذه النافذة أقصر، لذا احتفظ بمتغيرbestمنفصل. - قياس النافذة باستخدام
right - left. كلا الطرفين داخلها، لذا أضف واحدًا.
أسئلة شائعة3
ما هو التعقيد الزمني لاستبدال أطول محرف متكرر؟
يعمل حلّ النافذة الواحدة في زمن O(n)، حيث إن n هو طول s: يزور right كل حرف مرة واحدة، ويتحرك left مرة واحدة كحد أقصى في كل خطوة. ويستخدم مساحة إضافية قدرها O(1)، أي 26 عدّادًا وعددًا قليلًا من الأعداد الصحيحة.
ما الفرق بين هذا وبين أطول سلسلة فرعية دون أحرف مكررة؟
كلاهما يحرّك حدَّين على السلسلة النصية، لكن قاعدة النافذة الصالحة تختلف. في تلك الحالة، لا يجوز تكرار أي محرف، لذا تتقلص النافذة حتى يزول التكرار. هنا، يجب أن يكون الطول ناقص أكبر عدد تكرار لا يتجاوز k، لذا يمكن للنافذة أن تنزلق بطول ثابت.
هل يمكن حل هذه المسألة باستخدام البحث الثنائي؟
نعم. إذا كان مقطع فرعي بطول L قابلًا للوصول، فإن كل مقطع أقصر بداخله قابل للوصول أيضًا، لذا يمكنك إجراء بحث ثنائي على L. لكل قيمة L، حرّك نافذة ثابتة بهذا الطول وتحقّق مما إذا كان هناك موضع يحتاج إلى k تغييرات على الأكثر. هذا يستغرق O(n log n)، وهو أبطأ من حل النافذة الواحدة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def characterReplacement(s, k):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
s = "BAAACAB" k = 1
الإخراج المتوقع
5