Longest Repeating Character Replacement

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. Hence the resultant string will be “AAAA” or “BBBB” and the length of the longest substring containing the same letters will be 4 in both the cases.

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.

Approach

• The approach is to use a sliding window to maintain a substring with the maximum count of repeating characters.
• Dynamically adjust the window size by moving the left pointer when the number of non-repeating characters exceeds the allowed replacements (k).

Step 1: Initialization

• Initialize left and right pointers to the start of the string (left = 0, right = 0).
• Initialize maxLength to 0 to keep track of the maximum length of the substring.
• Initialize maxRepeatCount to 0 to keep track of the maximum count of repeating characters in the current window.
• Initialize a HashMap map1 to store the count of characters in the current window.

Step 2: Iterate through the string

• For each character at the right pointer:

• Update the count of the character in map1.
• Update maxRepeatCount to be the maximum of its current value and the count of the current character.
• Calculate nonrepeat as the number of characters in the current window minus maxRepeatCount.

• nonrepeat = (right - left + 1) - maxRepeatCount

Step 3: Check if the non-repeating characters exceed k:

• If nonrepeat > k, it means the number of characters that are not the most frequent character exceeds the allowed replacements (k).
• In this case, move the left pointer one step to the right and update the count of the character at the left pointer in map1.

Step 4: Update maxLength

• At each step, update maxLength to be the maximum of its current value and the length of the current window (right - left + 1).

Step 5: Return the result

• After iterating through the entire string, return the final value of maxLength.

Complexity

• Time Complexity:  O(N)
• Space Complexity: O(1)

Code

#Java Code

import java.util.HashMap;
import java.util.Map;

public class LongestRepeatingCharacterReplacement {
    public int characterReplacement(String s, int k) {

        int left = 0;
        int maxLength = 0;
        int maxRepeatCount = 0;
        int len = s.length();

        Map<Character, Integer> map1 = new HashMap<>();

        for (int right = 0; right < len; right++) {
            
            char curr = s.charAt(right);
            map1.put(curr, map1.getOrDefault(curr, 0) + 1);
            maxRepeatCount = Math.max(maxRepeatCount, map1.get(curr));
            int nonrepeat = (right - left + 1 ) - maxRepeatCount;

            if (nonrepeat > k) {
                map1.put(s.charAt(left), map1.get(s.charAt(left)) - 1);
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestRepeatingCharacterReplacement solution = new LongestRepeatingCharacterReplacement();

        String s1 = "ABAB";
        int k1 = 2;
        int result1 = solution.characterReplacement(s1, k1);

        System.out.println("Length of longest repeating substring: " + result1);
    }
}

Output

Length of longest repeating substring: 4