算法题/滑动窗口：无重复字符的最长子串的长度

题目

给定一个字符串，找出没有重复字符的最长子字符串的长度。

示例1：

输入：String="aabccbb"
输出：3
解释："abc"

示例2：

输入：String="abbbb"
输出：2
解释："ab"

解答1：滑动窗口

Java

import java.util.*;

class NoRepeatSubstring {
  public static int findLength(String str) {
    int windowStart = 0, maxLength = 0;
    Map<Character, Integer> charIndexMap = new HashMap<>();
    // 扩大窗口[windowStart, windowEnd]
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      char rightChar = str.charAt(windowEnd);
      // 如果map已包含“rightChar”，就从头开始缩小窗口，这样“rightChar”便只出现一次
      if (charIndexMap.containsKey(rightChar)) {
        // 在当前窗口中，我们将在其前一个索引之后没有任何“rightChar”，如果“windowStart”已经领先于“rightChar”的最后一个索引，我们将保留“windowStart”
        windowStart = Math.max(windowStart, charIndexMap.get(rightChar) + 1);
      }
      charIndexMap.put(rightChar, windowEnd); // 将'rightChar'添加到map中
      maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // 记住当前最长的长度
    }

    return maxLength;
  }

  public static void main(String[] args) {
    System.out.println("Length of the longest substring: " + NoRepeatSubstring.findLength("aabccbb"));
    System.out.println("Length of the longest substring: " + NoRepeatSubstring.findLength("abbbb"));
    System.out.println("Length of the longest substring: " + NoRepeatSubstring.findLength("abccde"));
  }
}

JavaScript

class NoRepeatSubstring {
  static findLength(str) {
    let windowStart = 0;
    let maxLength = 0;
    const charIndexMap = new Map();

    for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
      const rightChar = str.charAt(windowEnd);

      if (charIndexMap.has(rightChar)) {
        windowStart = Math.max(windowStart, charIndexMap.get(rightChar) + 1);
      }

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

    return maxLength;
  }
}

console.log("Length of the longest substring: " + NoRepeatSubstring.findLength("aabccbb"));
console.log("Length of the longest substring: " + NoRepeatSubstring.findLength("abbbb"));
console.log("Length of the longest substring: " + NoRepeatSubstring.findLength("abccde"));

Python

class NoRepeatSubstring:
    def findLength(string):
        windowStart = 0
        maxLength = 0
        charIndexMap = {}

        for windowEnd in range(len(string)):
            rightChar = string[windowEnd]

            if rightChar in charIndexMap:
                windowStart = max(windowStart, charIndexMap[rightChar] + 1)

            charIndexMap[rightChar] = windowEnd
            maxLength = max(maxLength, windowEnd - windowStart + 1)

        return maxLength

print("Length of the longest substring:", NoRepeatSubstring.findLength("aabccbb"))
print("Length of the longest substring:", NoRepeatSubstring.findLength("abbbb"))
print("Length of the longest substring:", NoRepeatSubstring.findLength("abccde"))

Go

package main

import (
	"fmt"
)

func findLength(str string) int {
	windowStart := 0
	maxLength := 0
	charIndexMap := make(map[byte]int)

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

		if _, ok := charIndexMap[rightChar]; ok {
			windowStart = max(windowStart, charIndexMap[rightChar]+1)
		}

		charIndexMap[rightChar] = windowEnd
		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("aabccbb"))
	fmt.Println("Length of the longest substring:", findLength("abbbb"))
	fmt.Println("Length of the longest substring:", findLength("abccde"))
}