Last updated on January 21st, 2025 at 02:08 am

Here, we see a Longest Repeating Character Replacement LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Sliding Window, Two Pointers

Companies

Pocketgems

Level of Question

Medium

Longest Repeating Character Replacement LeetCode Solution

1. Problem Statement

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.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Sliding Window. This pattern is commonly used for problems involving contiguous subarrays or substrings, where the goal is to find an optimal window (e.g., maximum or minimum size) that satisfies certain conditions.

3. Code Implementation in Different Languages

3.1 Longest Repeating Character Replacement C++

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        int i = 0, j = 0, maxi = 0;
        unordered_map<char,int>mp;
        int ans = -1;
        while(j < n)
        {
            mp[s[j]]++;
            maxi = max(maxi, mp[s[j]]);
            if((j-i+1) - maxi > k){
                mp[s[i]]--;
                i++;
            }
            ans = max(ans, (j-i+1));
            j++;   
        }
        return ans;
    }
};

3.2 Longest Repeating Character Replacement Java

class Solution {
    public int characterReplacement(String s, int k) 
    {
        int[] count=new int[26];
        int i=0,j=0,max=Integer.MIN_VALUE;
        int result=Integer.MIN_VALUE;
        while(i<s.length())
        {
            count[s.charAt(i)-'A']++;
            max=Math.max(max,count[s.charAt(i)-'A']);
            if(i-j-max+1>k)
            {
                count[s.charAt(j)-'A']--;
                j++;
            }
            result=Math.max(result,i-j+1);
            i++;
        }
        return result;
    }
}

3.3 Longest Repeating Character Replacement JavaScript

var characterReplacement = function(s, k) {
    var map = [26]
    let largestCount = 0, beg = 0, maxlen = 0;
    for(let end = 0; end < s.length; end++){
        const c = s[end]
        map[c] = (map[c] || 0) + 1
        largestCount = Math.max(largestCount, map[c])
        if(end - beg + 1 - largestCount > k){
            map[s[beg]] -= 1
            beg += 1
        }
        maxlen = Math.max(maxlen, end - beg + 1);
    }
    return maxlen;
};

3.4 Longest Repeating Character Replacement Python

class Solution(object):
    def characterReplacement(self, s, k):
        maxlen, largestCount = 0, 0
        arr = collections.Counter()
        for idx in xrange(len(s)):
            arr[s[idx]] += 1
            largestCount = max(largestCount, arr[s[idx]])
            if maxlen - largestCount >= k:
                arr[s[idx - maxlen]] -= 1
            else:
                maxlen += 1
        return maxlen

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)

• The algorithm is efficient because it uses the Sliding Window pattern to avoid redundant computations.
• The space complexity is constant because the problem is limited to uppercase English letters (A-Z), which means the frequency map/array size is fixed.