[Leetcode] 0424. Longest Repeating Character Replacement

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

內容目錄

Medium


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.

 

Example 1:

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

Example 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.
There may exists other ways to achieve this answer too.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length

Python

				
					# time complexity: O(n)
# space complexity: O(1)
from collections import defaultdict


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        result = 0
        left = right = 0
        freq = defaultdict(int)
        mostFreqChar = 0
        for right in range(len(s)):
            freq[s[right]] += 1

            mostFreqChar = max(mostFreqChar, freq[s[right]])

            if right - left + 1 - mostFreqChar > k:
                freq[s[left]] -= 1
                left += 1
            
            result = max(result, right - left + 1)

        return result


s = "AABABBA"
k = 1
print(Solution().characterReplacement(s, k))
				
			
zh_TW繁體中文