3. The maximum string without repeating characters is medium

Topic describes

Given a string, find the length of the smallest string that does not contain repeating characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3. Example 2: Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1. 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. Example 4: Input: s = "" Output: 0 Warning: 0 <= S. length <= 5 * 104 s The value consists of letters, digits, symbols, and SpacesCopy the code

Train of thought

  1. Define an object map
var lengthOfLongestSubstring = function (s) {
    let map = {}
    let l = 0
    let r = -1
    let res = 0
    while (l < s.length) {
        if (r + 1 < s.length && map[s[r + 1= =]]undefined) {
            map[s[++r]] = true
        } else {
            map[s[l++]] = undefined
        }
        res = Math.max(r - l + 1, res)
    }
    return res
};
Copy the code

Idea 2

var lengthOfLongestSubstring = function (s) {
    let len = s.length
    if(! len)return 0
    let has = {}
    let max = 0
    let left = 0
    for (let right = 0; right < len; right++) {
        let moveLeft = has[s[right]]
        if (moveLeft) {
            left = Math.max(left, moveLeft)
        }
        has[s[right]] = right + 1
        max = Math.max(max, right - left + 1)}return max
};
Copy the code

438. Find all letter heterotopic words in string medium 😄

Given a string s and a non-empty string p, find all substrings of the alphabetic alloword p in S and return the starting index of these substrings. The string contains only lowercase letters, and the length of the string s and p cannot exceed 20100. Note: An anagram word is a string with the same letters but different arrangements. Regardless of the order in which the answers are printed. Example 1: Input: s: "cbaebabacd" p: "ABC" Output: [0, 6] Explanation: The substring with the starting index equal to 0 is "CBA ", which is an anagram of" ABC ". The substring whose starting index is 6 is "bac", which is an anagram of "ABC". Example 2: Input: S: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring whose starting index equals 0 is "ab", which is an alphabetic alloword of "ab". The substring whose starting index equals 1 is "ba", which is an anagram of "ab". The substring whose starting index equals 2 is "ab", which is an alphabetic allotopic of "ab".Copy the code

The idea is all in the notes


// s: "cbaebabacd" p: "abc"
var findAnagrams = function (s, p) {
    let res = [];
    let left = 0,
        right = 0;
    let needs = {},
        windows = {};
    let match = 0;
    // Needs = {a: 1, b: 1, c: 1}
    for (let i = 0; i < p.length; i++) {
        needs[p[i]] ? needs[p[i]]++ : (needs[p[i]] = 1);
    }
	
    let needsLen = Object.keys(needs).length;
    
    while (right < s.length) {
        let c1 = s[right];
		
        if (needs[c1]) {
            windows[c1] ? windows[c1]++ : (windows[c1] = 1);
            if (windows[c1] == needs[c1]) {
                match++;
            }
        }
        right++;
        
        // Move left
        while (match === needsLen) {
        	// The key step of the comparison string needs to be sequential
            if (right - left == p.length) {
                res.push(left);
            }
            let c2 = s[left];
            if (needs[c2]) {
                windows[c2]--;
                if(windows[c2] < needs[c2]) { match--; } } left++; }}return res
};
Copy the code

Clock in