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

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;
    }
}

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

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;
    }

//竟然就这么做出来了
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        // write code here
        int left = 0;
        int max_len = 0;
        vector<int> count(256, 0);
        for (int i = 0; i < s.size(); i++) {
            count[s[i]]++;
            while (count[s[i]] > 1 && left < i) {
                count[s[left]]--;
                left++;
            }
            max_len = max(max_len, i - left + 1);
        }
        return max_len;
    }
};

package main
 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 动态规划
 * @param s string字符串
 * @return int整型
 */
func lengthOfLongestSubstring(s string) int {
    // write code here
    if len(s) == 0 {
        return 0
    }
 
    // dp[i] 表示以 s[i] 结尾的最长无重复子串长度
    dp := make([]int, len(s))
 
    // lastIndex 记录字符上一次出现的位置
    lastIndex := make(map[byte]int)
 
    dp[0] = 1           // 第一个字符子串长度为1
    lastIndex[s[0]] = 0 // 记录第一个字符的位置
    maxLen := 1         // 记录全局最长子串长度
 
    for i := 1; i < len(s); i++ {
        lastPos, found := lastIndex[s[i]]
 
        if found && lastPos >= i-dp[i-1] {
            // 如果字符在 dp[i-1] 子串内出现过
            dp[i] = i - lastPos
        } else {
            // 如果没有出现过或者不在 dp[i-1] 子串内
            dp[i] = dp[i-1] + 1
        }
 
        // 更新字符位置
        lastIndex[s[i]] = i
 
        // 更新最大长度
        if dp[i] > maxLen {
            maxLen = dp[i]
        }
    }
 
    return maxLen
}