算法题/滑动窗口：替换相同字符后的最长子串

题目

给定一个只包含小写字母的字符串，只允许用任何字母替换不超过k个字母，找出替换后拥有相同字母的最长子字符串的长度。

示例1：

输入：String="aabccbb", k=2
输出：5
解释："bbbbb"

示例2：

输入：String="abbcb", k=1
输出：4
解释："bbbb"

解答1：滑动窗口

Java

import java.util.*;

class CharacterReplacement {
  public static int findLength(String str, int k) {
    int windowStart = 0, maxLength = 0, maxRepeatLetterCount = 0;
    Map<Character, Integer> letterFrequencyMap = new HashMap<>();
    // 扩大范围[windowStart, windowEnd]
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      char rightChar = str.charAt(windowEnd);
      letterFrequencyMap.put(rightChar, letterFrequencyMap.getOrDefault(rightChar, 0) + 1);
      maxRepeatLetterCount = Math.max(maxRepeatLetterCount, letterFrequencyMap.get(rightChar));

      if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) {
        char leftChar = str.charAt(windowStart);
        letterFrequencyMap.put(leftChar, letterFrequencyMap.get(leftChar) - 1);
        windowStart++;
      }

      maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }

    return maxLength;
  }

  public static void main(String[] args) {
    System.out.println(CharacterReplacement.findLength("aabccbb", 2));
    System.out.println(CharacterReplacement.findLength("abbcb", 1));
    System.out.println(CharacterReplacement.findLength("abccde", 1));
  }
}

JavaScript

function findLength(str, k) {
  let windowStart = 0;
  let maxLength = 0;
  let maxRepeatLetterCount = 0;
  let letterFrequencyMap = new Map();

  for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
    let rightChar = str.charAt(windowEnd);
    letterFrequencyMap.set(
      rightChar,
      (letterFrequencyMap.get(rightChar) || 0) + 1
    );
    maxRepeatLetterCount = Math.max(
      maxRepeatLetterCount,
      letterFrequencyMap.get(rightChar)
    );

    if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) {
      let leftChar = str.charAt(windowStart);
      letterFrequencyMap.set(
        leftChar,
        letterFrequencyMap.get(leftChar) - 1
      );
      windowStart++;
    }

    maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
  }

  return maxLength;
}

console.log(findLength("aabccbb", 2));
console.log(findLength("abbcb", 1));
console.log(findLength("abccde", 1));

Python

def findLength(string, k):
    windowStart = 0
    maxLength = 0
    maxRepeatLetterCount = 0
    letterFrequencyMap = {}

    for windowEnd in range(len(string)):
        rightChar = string[windowEnd]
        letterFrequencyMap[rightChar] = letterFrequencyMap.get(rightChar, 0) + 1
        maxRepeatLetterCount = max(maxRepeatLetterCount, letterFrequencyMap[rightChar])

        if windowEnd - windowStart + 1 - maxRepeatLetterCount > k:
            leftChar = string[windowStart]
            letterFrequencyMap[leftChar] -= 1
            windowStart += 1

        maxLength = max(maxLength, windowEnd - windowStart + 1)

    return maxLength

print(findLength("aabccbb", 2))
print(findLength("abbcb", 1))
print(findLength("abccde", 1))

Go

package main

import (
	"fmt"
)

func findLength(str string, k int) int {
	windowStart := 0
	maxLength := 0
	maxRepeatLetterCount := 0
	letterFrequencyMap := make(map[byte]int)

	for windowEnd := 0; windowEnd < len(str); windowEnd++ {
		rightChar := str[windowEnd]
		letterFrequencyMap[rightChar]++
		maxRepeatLetterCount = max(maxRepeatLetterCount, letterFrequencyMap[rightChar])

		if windowEnd-windowStart+1-maxRepeatLetterCount > k {
			leftChar := str[windowStart]
			letterFrequencyMap[leftChar]--
			windowStart++
		}

		maxLength = max(maxLength, windowEnd-windowStart+1)
	}

	return maxLength
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	fmt.Println(findLength("aabccbb", 2))
	fmt.Println(findLength("abbcb", 1))
	fmt.Println(findLength("abccde", 1))
}