CodingGyan

Longest Repeating Character Replacement

medium Logic and Interview Sets

Problem

The word has only uppercase letters. You may change at most k letters to any other letter. Print the length of the longest part (continuous) that can be made of one repeated letter after at most k changes. Input: the word and k.

Constraints

  • 1 <= length <= 10^5
  • 0 <= k <= length

Examples

Input

AABABBA 1

Output

4

Solutions

Best approachTime O(n)Space O(1)

The window never shrinks, it only slides: it grows when it is valid and moves as a whole when it is not. The highest count seen is enough, because a bigger answer needs a bigger count. O(n).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Longest repeating part.
 * Input   : A word and k.
 * Output  : The length.
 * Approach: One window.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(String a, String b) {
        // Step 1: The window is s[left..right]. "counts" holds the letter counts. "mostCommon" is the highest count seen in any window so far.
        int k = Integer.parseInt(b);
        int[] counts = new int[26];
        int left = 0;
        int mostCommon = 0;
        int best = 0;
        for (int right = 0; right < a.length(); right++) {
            mostCommon = Math.max(mostCommon, ++counts[a.charAt(right) - 'A']);
            // Step 2: The letters to change are the window size minus the most common letter. If that is more than k, move the left side.
            if (right - left + 1 - mostCommon > k) {
                counts[a.charAt(left++) - 'A']--;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(solve(a, b));
    }
}
Hints (2)
  1. How many letters must change in a window?
  2. Why does the window never shrink?

Try these next