最长不含重复字符的子字符串

from queue import deque
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        if not s:
            return 0
        q = deque()
        # 初始无重复最长子串长度
        max_substr = 0
        for i in s:
            if i not in q:
                q.append(i)
                # 更新max_substr
                if len(q) > max_substr:
                    max_substr = len(q)
            else:
                # 从队列中弹出重复元素i以及i之前的所有元素
                while i in q:
                    q.popleft()
                # 弹出之后将i入队
                q.append(i)
        return max_substr

import java.util.*;
public class Solution {
    public int lengthOfLongestSubstring (String s) {
        // 定义最大长度
        int max=0;
        // 定义start指针，初始值为-1是考虑到length=1的输入
        int start=-1;
        // 定义hashmap,key为字符，value为最后一次出现的位置
        HashMap<Character,Integer> map = new HashMap<>();
        // 遍历字符串
        for(int i=0;i<s.length();i++){
            char cur = s.charAt(i);
            // 只有当重复元素出现在start后方时，才更新start（避免start向前更新）
            if(map.containsKey(cur) && map.get(cur) > start){
                start = map.get(cur);
            }
            // 实时更新map
            map.put(cur,i);
            // 更新最大长度
            max = Math.max(max, i-start);
        }
        // 返回最大长度
        return max;
    }
}

public int lengthOfLongestSubstring(String s) {
        int b = 0;
        int key = 0;
        List<Character> res = new ArrayList<>();
        while (b != s.length()) {
            if (res.contains(s.charAt(b))){
                List<Character> code = new ArrayList<>();
                for (Character re : res) {
                    if (re == s.charAt(b)) {
                        code.add(re);
                        break;
                    } else code.add(re);
                }
                res.removeAll(code);
                res.add(s.charAt(b));
                b++;
            }else {
                res.add(s.charAt(b));
                b++;
            }
            key = Math.max(key,res.size());
        }
        return key;
    }

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return int整型
 */
func lengthOfLongestSubstring(s string) int {
	// write code here
	var char2Index = make(map[int32]int, len(s))
	var maxSub = 0
	var currentSubLen = 0

	var getMax = func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	var left int
	for index, char := range s {
		if charIdx, exist := char2Index[char]; exist {
			if charIdx < left {
				currentSubLen += 1
			} else {
				maxSub = getMax(currentSubLen, maxSub)
				currentSubLen = index - charIdx
				left = charIdx + 1
			}
		} else {
			currentSubLen += 1
		}
		char2Index[char] = index
	}
	maxSub = getMax(currentSubLen, maxSub)
	return maxSub
}

function lengthOfLongestSubstring(s) {
    // write code here
    if (!s) return 0;
    let dic = new Map();
    let dp = [1];
    let m = 1;
    dic.set(s[0], 0);
    for (i = 1; i < s.length; i++) {
        let j = dic.get(s[i]);
        dp[i] = j === undefined || dp[i - 1] < i - j ? dp[i - 1] + 1 : i - j;
        dic.set(s[i], i);
        m = Math.max(m, dp[i]);
    }
    return m;
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        // 时间复杂度O(N)，空间复杂度O(N)
        unordered_set<char> hash;
        int left = 0, right = 0, res = 0;
        while (right < s.size()) {
            while (hash.find(s[right]) != hash.end()) {
                hash.erase(s[left]);
                ++left;
            }
            hash.insert(s[right]);
            ++right;
            res = max(res, right - left);
        }
        return res;
    }
};

public int lengthOfLongestSubstring(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for (int i = 0; i < 128; i++) last[i] = -1;

        int start = 0;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i);
            // 控制窗口开始位置
            start = Math.max(start, last[index] + 1);
            // 判断哪个窗口更长
            res = Math.max(res, i - start + 1);
            // 记录出现位置
            last[index] = i;
        }

        return res;
    }

 public int lengthOfLongestSubstring (String s) {
        // write code here
        HashMap<Character, Integer> map = new HashMap<>();
        int res = 0;
        int l = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            } else {
                map.put(s.charAt(i), 1);
            }
            //重复了就一直移动左边界 直到不重复
            while (map.get(s.charAt(i)) > 1) {
                map.put(s.charAt(l), map.get(s.charAt(l)) - 1);
                l++;
            }
            res = Math.max(res, i - l + 1);
        }
        return res;
    }
}

 public int lengthOfLongestSubstring (String s) {
     int max=0;
        int start=0;
        char[] chars = s.toCharArray();
        Set<Character> set = new HashSet<>();
        for (int end = 0; end < chars.length; end++) {
            while (set.contains(chars[end])){
                set.remove(chars[start]);
                start++;
            }
            set.add(chars[end]);
            max=Math.max(max,end-start+1);
        }
        return max;
    }

    public int lengthOfLongestSubstring (String s) {
        // write code here
        HashMap<Character, Integer> mp = new HashMap<>();
        int res = 0;
        if(s.length() <= 1){
            return s.length();
        }
        int left = 0, right = 0;
        while(right < s.length()){
            if(mp.containsKey(s.charAt(right))){
                mp.put(s.charAt(right), mp.get(s.charAt(right)) + 1);
            } else {
                mp.put(s.charAt(right), 1);
            }
            if(mp.get(s.charAt(right)) > 1){
                // 因为每次subring提取出来的字符串索引值都是从0开始，
                // 所以需要加上左边界left，才能表示s.charAT(right)字符在s中的索引位置
                int index = s.substring(left, right).indexOf(s.charAt(right)) + left;
                mp.put(s.charAt(right), mp.get(s.charAt(right))-1);  // 保证字符left,right区间的字符只出现一次。如果不做这一步，假设abcac,此时a重复了，在区间[0,4]之间，a出现两次，移动left到1时，a在[1,4]之间只出现一次，如果不-1，则还是两次，就会判定错误。
                res = Math.max(res, right - left);
                left = index + 1;
            }
            right++;
        }
        // 会出现一种情况，right一直到结束，都没有重复，此时就无法进入if条件判断长度
        // 需要在循环结束时，判断最后一个是否重复？ 重复，说明已经进入循环内的if判断过
        // 不重复，说明还需要再进行判断一次，判断res 与 当前right - left 长度
        return mp.get(s.charAt(right-1)) == 1 ? res = Math.max(res, right - left) : res;

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # write code here
        dp = [1]
        hashmap = {s[0]: 0}

        for i in range(1, len(s)):
            if s[i] not in hashmap:  # 最长子串+1
                dp.append(dp[i - 1] + 1)
                hashmap[s[i]] = i
            else:
                index = hashmap[s[i]]
                hashmap[s[i]] = i
                dp.append(min(i - index, dp[i - 1] + 1))
        return max(dp)