2019-11-03 无重复字符的最长子串

package com.example.demo.domain.entity;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * @author ken
 *
 */
public class Solution {
    /**
     * 思路：
     * 1.使用hashSet保存已有的不含重复字符的字符串
     * 2.startIndex标识字串开始位置，endIndex标识字串结束位置
     * 3.startIndex,endIndex从初始位置滑动
     * 4.如果endIndex位置的字符串不在hashSet中，继续向右移动
     * 5.如果endIndex位置的字符串在hashSet中，hashSet从startIndex位置元素开始移除，直至不包含endIndex的元素
     * 6.在上面过程中记录最大字串长度
     * @param s
     * @return
     */
     public static int lengthOfLongestSubstring(String s) {
         int len = s.length();
    
        int startIndex = 0;
        int endIndex = 0;
        int max = 0;
        Set<Character> set = new HashSet<>();
        
        while(startIndex < len && endIndex < len){
            
            if(!set.contains(s.charAt(endIndex))){
                set.add(s.charAt(endIndex));
                endIndex++;
                max = Math.max(max, set.size());
            }else{
                set.remove(s.charAt(startIndex));
                startIndex ++;
            }
            
        }
        
         return max;
     }
     public static void main(String[] args) {
         int l = lengthOfLongestSubstring("abcabcbb");
         System.out.println(l);
    }
}