SOURCE

// 最小字串
// 给你一个字符串S、一个字符串T，请在字符串S里面找出：包含T所有字母的最小子串。
// 示例：
// 输入：s＝＂ADOBECODEBANC＂，T＝＂ABC＂
// 输出：＂BANC＂
// 说明：
// ·如果S中不存这样的子串，则返回空字符串
// ·如果S中存在这样的子串，我们保证它是唯一的答案。


function subChars (source, target) {
    let targetDic = {}, targetArr = target.split("")
    console.log(targetArr)
    for (let index in targetArr) {
        targetDic[targetArr[index]] = 1
    }
    let searchDic = {}, result = ""
    let left = 0, right = 0, found = 0
    while (right < source.length) {
        // search++
        if(searchDic[source[right]]) {
            searchDic[source[right]]++
        } else {
            searchDic[source[right]] = 1
        }
        // 如果右侧滑标所指属于目标字符
        if(targetDic[source[right]]) {
            if(searchDic[source[right]] == 1)
                found ++
            // 如果所有目标字符已经集齐
            // 可以开始从左面削减长度，移动 左边 滑标
            while(found == target.length) {
                searchDic[source[left]] --
                // 移走的字符属于目标字符
                if(targetDic[source[left]]) {
                    // 移走的字符属于目标字符 并且 移光了
                    if(searchDic[source[left]] == 0) {
                        found --
                        // 移走的字符属于目标字符 并且 移光了
                        // 则当前窗口（source[left, right]）不包含所有目标字符串了
                        if(found < target.length) {
                            if(result.length == 0 || (result.length >= right - left + 1)) {
                                result = source.substr(left, right - left + 1)
                            }
                        }
                    }
                }
                left ++
            }
        }
        right ++
    }
    return result
}

let sub = subChars("ADOBECODEBANC", "ABC")
console.log(sub)


// 给定两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。
// 换句话说，第一个字符串的排列之一是第二个字符串的子串。
// 示例1：
// 输入：s1＝ ＂ab＂ s2 ＝ ＂eidbaooo＂
// 输出：True
// 解释：s2 包含s1的排列之一（＂ba＂）．
// 示例2：
// 输入：s1＝ ＂ab＂ s2 ＝ ＂eidboaoo＂
// 输出：False


function containChars (source, target) {
    let targetDic = {}, targetArr = target.split("")
    console.log(targetArr)
    for (let index in targetArr) {
        targetDic[targetArr[index]] = 1
    }
    let searchDic = {}, result = ""
    let left = 0, right = 0, found = 0
    while (right < source.length) {
        // search++
        searchDic[source[right]] ? searchDic[source[right]]++ : searchDic[source[right]] = 1
        // 如果右侧滑标所指属于目标字符
        if(targetDic[source[right]]) {
            if(searchDic[source[right]] == 1)
                found ++
            // 如果所有目标字符已经集齐
            // 可以开始从左面削减长度，移动 左边 滑标
            while(found == target.length) {
                searchDic[source[left]] --
                // 移走的字符属于目标字符
                if(targetDic[source[left]]) {
                    // 移走的字符属于目标字符 并且 移光了
                    if(searchDic[source[left]] == 0) {
                        found --
                        // 移走的字符属于目标字符 并且 移光了
                        // 则当前窗口（source[left, right]）不包含所有目标字符串了
                        if(found < target.length) {
                            if(result.length == 0 || (result.length >= right - left + 1)) {
                                result = source.substr(left, right - left + 1)
                            }
                        }
                    }
                }
                left ++
            }
        }
        right ++
    }
    return result.length > target.length ? false : true
}

let contains = containChars("eidboaoo", "ba")
console.log(contains)




// 给定一个字符串s和一个非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子
// 串的起始索引。
// 字符串只包含小写英文字母，并且字符串s和p的长度都不超过20100。
// 说明：
// ·字母异位词指字母相同，但排列不同的字符串。
// ·不考虑答案输出的顺序。
// 示例1：
// 输入：
// s: "cbaebabacd" p: "abc"
// 输出：
// [0,6]
// 解释：
// 起始索引等于0的子串是＂cba＂，它是＂abc＂的字母异位词。
// 起始索引等于6的子串是＂bac＂，它是＂abc＂的字母异位词

function indexOfChars (source, target) {
    let searchedDic = {}, targetDic = {}
    let targetArr = target.split("")
    for (let i in targetArr) {
        targetDic[targetArr[i]] = 1
    }
    let start = 0, end = 0, indexArr = [], count = 0
    while (end < source.length) {

        searchedDic[source[end]] ? searchedDic[source[end]] ++ : searchedDic[source[end]] = 1
        if(targetDic[source[end]]) {
            searchedDic[source[end]]==1 ? count ++ : count
            while (count == target.length) {
                searchedDic[source[start]] --
                if (targetDic[source[start]]) {
                    if(searchedDic[source[start]] == 0) {
                        count --
                        if(count < target.length) {
                            let result = source.slice(start, end+1)
                            if(result.length == target.length) {
                                indexArr.push(start)
                            }
                        }
                    }
                }
                start ++
            }
        }
        end ++
    }
    return indexArr
}

let indexs = indexOfChars("cbaebabacd", "abc")
console.log(indexs)







// 输出：3
// 解释：因为无重复字符的最长子串是＂abc＂，所以其长度为3。
// 示例2：
// 输入：
// "bbbbb"
// 输出：1
// 解释：因为无重复字符的最长子串是＂b＂，所以其长度为 1。
// 示例3：
// 输入：
// "pwwkew"
// 输出：3
// 解释：因为无重复字符的最长子串是＂wke＂，所以其长度为 3。
// 请注意，你的答案必须是 子串的长度，＂pwke＂是一个子序列，不是子串

function longestUniqueChars (source) {
    let sourceArr = source.split("")
    let searchedDic = {}
    let start = 0, end = 0, longestLen = 0
    while(end < source.length) {
        searchedDic[source[end]] || (searchedDic[source[end]] = 0)
        searchedDic[source[end]]++
        console.log(searchedDic)
        if (searchedDic[source[end]] > 1) {
            if (longestLen < end - start) {
                longestLen = end - start
            }
            searchedDic = {}
            start = end
        }
        end ++
    }
    return longestLen
}

let length = longestUniqueChars("cbaebabacd")
console.log(length)