3. Longest Substring Without Repeating Characters

题目：

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

　Input: "pwwkew"

　Output: 3

　Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解答：

方法一：遍历所有可能的截取字符串，判断是否为不包含重复元素的字符串

java代码实现

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

public class LongestSubstring {

    private static int lengthOfLongestSubstring(String s){
        int n = s.length();
        int ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j <= n; j++){
                if(allUnique(s, i, j)){
                    ans = Math.max(j - i, ans);
                }
            }
        }
        return ans;
    }

    private static boolean allUnique(String s, int start, int end){
        Set<Character> set = new HashSet<>();
        for(int i = start; i < end; i++){
            Character ch = s.charAt(i);
            // set.contains(Object o)底层依赖equals()方法和hashcode()方法，如果是对象可以重写这两个方法
            // 参见https://blog.csdn.net/gao2628688/article/details/80947588
            // Character源码：public static int hashCode(char value) {return (int)value;}
            if(set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }

    public static void main(String[] args){
        int i = lengthOfLongestSubstring("mnsopakjn");
        System.out.println(i);
    }
}

c++实现：

方法二：滑动窗口：最长的字符串肯定出现在两个相同的元素中间，或者在最前面，或者在最后面，滑动窗口的范围[i, j)，当发现当前的集合包含重复元素时，可以将左边界向右移动，直到左边界到达该重复元素的前一个元素为止，并删除集合中左边界的元素，将右边界中该元素添加进集合，再继续统计最长的长度。

java实现：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int i = 0, j = 0, ans = 0;
        Set<Character> set = new HashSet<>();
        while(i < n && j < n){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }else{
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

 方法三:优化的滑动窗口：遇到重复的元素时，之间将左边界移动到该重复元素出现的上次位置

java实现:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);    // 防止出现 baab这种情况，检测到最后一个b，又将左边界移动到最左边的b，左边界只能向前移动
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);     // 没有插入，已经存在更新键对应的元素值
        }
        return ans;
    }
}