Given a string, find the length of the smallest string that does not contain repeated characters. Leetcode 3.

The length of the longest string without repeating characters

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code

Example 2:

Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the code

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: Since the oldest string without repeating characters is "wKE", its length is 3. Note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring.Copy the code

Example 4:

Input: s = "output: 0Copy the code

The problem solving method

In this method, the current content is not repeated through the front and back double Pointers, and each time it will judge whether the latest start value is needed. According to the position of the back pointer – the position of the front pointer + 1, and compare with the current maximum value, to get the final result.

function lengthOfLongestSubstring(str) {
    if (str === "") return 0;
    let start = 0, maxLen = 0;
    const map = new Map();
    const len = str.length;
    for(let i = 0; i < len; i++) {
        const c = str[i];
        if (map.has(c)) {
            start = Math.max(map.get(c) + 1, start)
        }
        map.set(c, i);
        maxLen = Math.max(i - start + 1, maxLen);
    }
    return maxLen;
}
Copy the code

The oldest string without repeating characters

Try modifying this problem to find out what the oldest string is without repeating characters. For now, consider the case where there is only one oldest string.

function lengthOfLongestSubstring(str) { if (str === "") return null; let start = 0, maxLen = 0, resStr = null; const map = new Map(); const len = str.length; for(let i = 0; i < len; i++) { const c = str[i]; if (map.has(c)) { start = Math.max(map.get(c) + 1, start); } map.set(c, i); If (i-start + 1 > maxLen) {resStr = str.slice(start, I + 1); } maxLen = Math.max(i - start + 1, maxLen); } return resStr; }Copy the code

conclusion

At present, this method is more convenient.