Leetcode 424 Longest Repeating Character Replacement

Soru

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Örnek 1

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Örnek 2

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Çözüm

• Bir string içinde belirli bir sayıda karakter değişikliği yaparak elde edilebilecek en uzun tekrar eden karakter dizisini bulmanızı ister. Bu soruda, maksimum k karakteri değiştirerek bir karakteri diğer bir karakterle değiştirebilirsiniz, ve amacınız, en uzun aynı karakter dizisini (tek tip dizi) oluşturmaktır.
• Girdi: Bir string s ve bir tam sayı k.
• Çıktı: En fazla k karakter değiştirerek elde edilebilecek en uzun tekrar eden karakter dizisinin uzunluğu.
• Bu problem, kaydırmalı pencere (sliding window) veya iki işaretçi tekniği kullanılarak çözülebilir. Buradaki temel fikir, bir pencere içinde en fazla k değişiklik ile oluşturulabilecek en uzun alt diziyi bulmaktır. Pencere boyutu, penceredeki en yaygın karakterin sayısına ve k’ya bağlı olarak dinamik olarak ayarlanır.
• Çalışma Mekanizması:
• Değişkenlerin İnitialize Edilmesi: count karakter sayılarını tutar, max_count penceredeki en sık tekrar eden karakterin sayısını, max_length ise en uzun alt dizinin uzunluğunu tutar.
• Döngü İle İşlem: right işaretçisi string boyunca ilerler ve her karakter için count güncellenir. Ayrıca, her adımda max_count güncellenir.
• Pencere Kontrolü: Eğer pencerenin boyutu eksi içindeki en yaygın karakterin sayısı k’dan büyükse, bu, daha fazla değişiklik gerektiği anlamına gelir. Bu durumda, left işaretçisi artırılarak pencere daraltılır.
• Maksimum Uzunluğun Güncellenmesi: Pencere uygun boyutta olduğunda, max_length güncellenir.
• Sonuç Dönüşü: Tüm işlemler tamamlandığında, hesaplanan maksimum uzunluk döndürülür.

Code

class Solution:
    def characterReplacement(self, s, k):
        count = {}
        max_length = 0
        max_count = 0
        left = 0
        
        for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1
            max_count = max(max_count, count[s[right]])

            # Pencere boyutu - içindeki en yaygın karakterin sayısı > k ise pencereyi daralt
            while (right - left + 1) - max_count > k:
                count[s[left]] -= 1
                left += 1
            
            # Mevcut pencere boyutu maksimum uzunluğu güncelle
            max_length = max(max_length, right - left + 1)
        
        return max_length

        
        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n string s’nin uzunluğudur. Her karakter için sabit zaman işlemi yapılır.
• Space complexity (Alan Karmaşıklığı) : O(1), karakter sayısını tutmak için kullanılan alan genellikle sabittir (ASCII veya Unicode gibi sınırlı bir karakter seti varsayılırsa).