Sliding Window

Longest Substring with Same Letters after Replacement

Rajeev SinghAlgorithms1 mins read

Longest Substring with Same Letters after Replacement

Problem Statement

Given a string with lowercase letters only. If you are allowed to replace at most k letters with any letter, find the length of the longest substring having the same letters after replacement.

Example 1:

Input: s="abcababb", k=2
Output: 5
Explanation: Replace the two 'a' with 'b' in the substring 'ababb' to get the longest substring "bbbbb" with same letters.

Example 2:

Input: s="abccde", k=1
Output: 3
Explanation: Replace the 'b' or 'd' with 'c' to get the the longest substring "ccc" with same letters.

Solution

This problem is a variant of the problem Longest Substring without repeating characters. We will use a similar sliding-window technique to solve this problem.

  • Consider each substring as a sliding window.
  • Start with a sliding window of size 1 (windowStart=0, windowEnd=0).
  • Initialize a HashMap that stores the character count for each character in the current window.
  • Iterate over the string and add one letter at a time to the window.
  • We will also keep track of the letter that repeats the maximum number of times in the current window. Let’s call it maxRepeatLetterCount.
  • In each iteration, we know that we have a window with one letter repeating maxRepeatLetterCount times. Since we only have k replacements allowed, we should keep aside the letter that repeats the most number of times and replace the remaining letters.
    • If the remaining letters in the window are less than or equal to k then we can replace them all.
    • Otherwise, we need to shrink the window as we are not allowed to replace more than k letters. 
class LongestSubstringWithSameLettersAfterReplacement {
    private static int findLengthOfLongestSubstringWithSameLettersAfterReplacement(String s, int k) {
        int n = s.length();

        // length of the longest substring with same letters after replacement.
        int maxLen = -1;

        // character count for each character in the current window
        Map<Character, Integer> windowCharCount = new HashMap<>();

        int windowStart = 0;
        for(int windowEnd = 0; windowEnd < n; windowEnd++) {
            // Add the next character to the window
            char c = s.charAt(windowEnd);
            windowCharCount.put(c, windowCharCount.getOrDefault(c, 0) + 1);

            // Calculate max repeating character in the current window
            int maxRepeatLetterCount = getMaxRepeatLetterCount(windowCharCount);
            
            /*
            The current window has a letter that repeats 'maxRepeatLetterCount' times.
            If the remaining letters in the window are less than or equal to k then we can replace them all.
            Otherwise, we need to shrink the window since we are not allowed to replace more than 'k' letters. 
            */
            while(windowEnd-windowStart+1 - maxRepeatLetterCount > k) {
                char leftChar = s.charAt(windowStart);
                windowCharCount.put(leftChar, windowCharCount.get(leftChar) - 1);
                windowStart++; // Shrink the window                
            }

            // At this point, the number of remaining letters in the window are less than or equal to k. 
            // So we can replace them all to obtain a substring with same letters.
            // Update the max length if the current window size is longer.
            maxLen = Math.max(maxLen, windowEnd-windowStart+1);
        }

        return maxLen;  
    }

    private static int getMaxRepeatLetterCount(Map<Character, Integer> charCount) {
        int maxCount = 0;
        for(int count: charCount.values()) {
            if(maxCount < count) {
                maxCount = count;
            }
        }    
        return maxCount;
    }


    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        String s = keyboard.next();
        int k = keyboard.nextInt();
        keyboard.close();
        
        System.out.printf("Longest substring with same letters after replacement = %d%n", findLengthOfLongestSubstringWithSameLettersAfterReplacement(s, k));
    }
}