算法题/滑动窗口：k个不同字符的最长子串

题目

给定一个字符串，找出不超过K个不同字符的最长子字符串的长度。你可以假设k是小于或等于给定字符串的长度。

示例1：

输入：String="araaci", K=2
输出：4
解释："araa"

示例2：

输入：String="cbbebi", K=3
输出：5
解释："cbbeb" 或者 "bbebi"

解答1：

Java

import java.util.*;

class LongestSubstringKDistinct {
  public static int findLength(String str, int k) {
    if (str == null || str.length() == 0 || str.length() < k)
      throw new IllegalArgumentException();

    int windowStart = 0, maxLength = 0;
    Map<Character, Integer> charFrequencyMap = new HashMap<>();
    // 接下来的循环我们尝试扩大范围 [windowStart, windowEnd]
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      char rightChar = str.charAt(windowEnd);
      charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);
      // 收缩滑动窗口，直到有k个不同的元素在charFrequencyMap中
      while (charFrequencyMap.size() > k) {
        char leftChar = str.charAt(windowStart);
        charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
        if (charFrequencyMap.get(leftChar) == 0) {//当字符出现频率为0时，需要从hashmap中删除该字符
          charFrequencyMap.remove(leftChar);
        }
        windowStart++; //收缩窗口
      }
      //记住滑动窗口的最大长度
      maxLength = Math.max(maxLength, windowEnd - windowStart + 1); 
    }

    return maxLength;
  }

  public static void main(String[] args) {
    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("araaci", 2));
    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("araaci", 1));
    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("cbbebi", 3));
  }
}

JavaScript

class LongestSubstringKDistinct {
  static findLength(str, k) {
    if (str === null || str.length === 0 || str.length < k)
      throw new Error("Invalid arguments");

    let windowStart = 0, maxLength = 0;
    const charFrequencyMap = new Map();
    for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
      const rightChar = str.charAt(windowEnd);
      charFrequencyMap.set(rightChar, (charFrequencyMap.get(rightChar) || 0) + 1);

      while (charFrequencyMap.size > k) {
        const leftChar = str.charAt(windowStart);
        charFrequencyMap.set(leftChar, charFrequencyMap.get(leftChar) - 1);
        if (charFrequencyMap.get(leftChar) === 0) {
          charFrequencyMap.delete(leftChar);
        }
        windowStart++;
      }

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

    return maxLength;
  }
}

console.log("Length of the longest substring: " + LongestSubstringKDistinct.findLength("araaci", 2));
console.log("Length of the longest substring: " + LongestSubstringKDistinct.findLength("araaci", 1));
console.log("Length of the longest substring: " + LongestSubstringKDistinct.findLength("cbbebi", 3));

Python

class LongestSubstringKDistinct:
    def findLength(string, k):
        if string is None or len(string) == 0 or len(string) < k:
            raise ValueError("Invalid arguments")

        windowStart = 0
        maxLength = 0
        charFrequencyMap = {}
        
        for windowEnd in range(len(string)):
            rightChar = string[windowEnd]
            charFrequencyMap[rightChar] = charFrequencyMap.get(rightChar, 0) + 1

            while len(charFrequencyMap) > k:
                leftChar = string[windowStart]
                charFrequencyMap[leftChar] -= 1
                if charFrequencyMap[leftChar] == 0:
                    del charFrequencyMap[leftChar]
                windowStart += 1

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

        return maxLength


print("Length of the longest substring:", LongestSubstringKDistinct.findLength("araaci", 2))
print("Length of the longest substring:", LongestSubstringKDistinct.findLength("araaci", 1))
print("Length of the longest substring:", LongestSubstringKDistinct.findLength("cbbebi", 3))

Go

package main

import (
	"fmt"
)

func findLength(str string, k int) int {
	if str == "" || len(str) < k {
		panic("Invalid arguments")
	}

	windowStart := 0
	maxLength := 0
	charFrequencyMap := make(map[byte]int)

	for windowEnd := 0; windowEnd < len(str); windowEnd++ {
		rightChar := str[windowEnd]
		charFrequencyMap[rightChar]++

		for len(charFrequencyMap) > k {
			leftChar := str[windowStart]
			charFrequencyMap[leftChar]--
			if charFrequencyMap[leftChar] == 0 {
				delete(charFrequencyMap, 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("Length of the longest substring:", findLength("araaci", 2))
	fmt.Println("Length of the longest substring:", findLength("araaci", 1))
	fmt.Println("Length of the longest substring:", findLength("cbbebi", 3))
}