【LeetCode题解---003】Longest Substring Without Repeating Characters

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

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

Input: "pwwkew"Output: 3Explanation: 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.

public static boolean unique(String string, int start, int end) {

    Set<Character> set = new HashSet<>();
    char[] array = string.toCharArray();
    for (int i = start; i < end; i++) {
        if (set.contains(array[i])) {
            return false;
        }
        set.add(array[i]);
    }
    return true;
}

/**
 * 就是三个for循环 求解，去掉非法的判断 复杂度达到了 O(n^3)
 * @param s
 * @return
 */
public static int lengthOfLongestSubstring2(String s) {
    int length = s.length();
    int result = 0;
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j <= length; j++) {
            if (unique(s, i, j)) {
                result = Math.max(result, j - i);
            }
        }
    }
    return result;
}

public static int lengthOfLongestSubstring3(String s) {
    Map<Character, Integer> map = new HashMap<>(s.length());
    char[] array = s.toCharArray();
    int i, max = 0, pre = -1;
    // 初始化开始的下标
    for (i = 0; i < array.length; i++) {
        map.put(array[i], -1);
    }
    for (i = 0; i < array.length; i++) {
        //更新map中各个字符的下标
        pre = Math.max(pre, map.put(array[i], i));
        //保存暂时的最大无重复子串长度
        max = Math.max(max, i - pre);
        //计算差值后继续更新
        map.put(array[i], i);
    }
    return max;
}

public static int lengthOfLongestSubstring(String s) {
    if (s == null) {
        return 0;
    }
    if (s.length() == 0) {
        return 0;
    }
    Map<Character, Integer> map = new HashMap<>(s.length());
    int max = 0;
    // 转换成字符数组
    char[] array = s.toCharArray();
    for (int i = 0, j = 0; i < array.length; ++i) {
        // map 中已经有这个字符
        if (map.containsKey(array[i])) {
            j = Math.max(j, map.get(array[i]) + 1);
        }
        // 给每个字符一个下标
        /*
            如           p w w k e w
            则对应下标是  0 1 2 3 4 5
         */
        map.put(array[i], i);
        max = Math.max(max, i - j + 1);
    }
    return max;
}

 class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
left, right = 0, 0
chars = set()
res = 0
while left < len(s) and right < len(s):
if s[right] in chars:
if s[left] in chars:
chars.remove(s[left])
left += 1
else:
chars.add(s[right])
right += 1
res = max(res, len(chars))

return res

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        left, right = 0, 0
        res = 0
        chars = dict()
        for right in range(len(s)):
            if s[right] in chars:
                left = max(left, chars[s[right]] + 1)
            chars[s[right]] = right
            res = max(res, right - left + 1)
        return res