Longest Repeating String After K Replacement Using Python 🐍| Coding Interview | Sliding Window Pattern

Longest Substring after 2 Replacements

We will discuss a little bit about a naive approach to solving this problem before moving on to an efficient solution. The strategy for this problem is similar to the Smallest Subarray With a Given Sum. I have tried to explain these concepts in simple terms, hope you find the effort useful.

This problem has been asked by Meta, Uber, Amazon, and Adobe.

If you are preparing for an upcoming coding interview you may want to check out my 30 Days preparation plan, this article belongs to that plan.

Contents

1. Description
2. Brute Force Solution
3. Efficient Solution
4. Code
5. Time & Space Complexity

Description

Given a string S with only uppercase letters and you are allowed to make at most K replacements with other uppercase letters. Find the length of the longest substring containing the same letter after replacement.

Example 1:
Input: S = ABBCAB, K = 2
Output: 5
Explanation: The longest substring after at most 2 replacements is BBBBB from BBCAB where we replaced 'C' and…