Categories
Uncategorized

438. Find All Anagrams in a String Leetcode Javascript Solution

The Problem:

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

The Solution:

var findAnagrams = function(s, p) {
    let set = new Map()
    for(let i = 0; i < p.length; i++){
        if(!set.has(p[i])){
            set.set(p[i],1)
        } else{
            set.set(p[i],set.get(p[i]) + 1)
        }
    }
   // console.log(set)
    let ans = []
     let left = 0, right = 0, count = set.size
     while (right < s.length){
         if(set.has(s[right])){
             set.set(s[right],set.get(s[right]) - 1)
             if(set.get(s[right])== 0){
                 count--
             }
         }
         while(count == 0){
             if(set.has(s[left])){
                    set.set(s[left],set.get(s[left]) + 1)
                 if(set.get(s[left]) > 0){
                 count++
             }
             }
             if(right - left +1 == p.length){
                 ans.push(left)
             }
             left++
         }
         right++
     }
    return ans
};
Categories
Uncategorized

76. Minimum Window Substring Leetcode Javascript Solution

The Problem:

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "a", t = "a"
Output: "a"

Constraints:

  • 1 <= s.length, t.length <= 105
  • s and t consist of English letters.

The Solution:

var minWindow = function(s, t) {
    if( !s || s.length < t.length){ return ""}
    let left = 0, right = 0, start,end, index = 0, min = 99999;
    let charsT = new Map()
    let charsS = new Map()
    for(let i = 0; i < t.length; i++){
        if(!charsT.get(t[i])){
            charsT.set(t[i],1)
        } else {
            charsT.set(t[i],charsT.get(t[i])+1)
        }
    }
    //console.log(charsT)
    while(right < s.length){
        if(!charsS.get(s[right])){
                    charsS.set(s[right],1)
                } else {
                    charsS.set(s[right],charsS.get(s[right])+1)
                }
        if(charsT.get(s[right]) && charsS.get(s[right]) == charsT.get(s[right]) ){
            index++
        }
        while(left <= right && index == charsT.size){
              //  console.log("left " + left + " right " + right)
            if(right - left + 1 < min){
                min = right - left + 1
                start = left
                end = right
             //   console.log("start " + start + " end " + end)
            }
            //console.log(charsS)
                let c = s[left]
                if(charsS.get(c)){
                   charsS.set(c,charsS.get(c)-1)
               //  console.log("eliminated start char: ")
                 // console.log(charsS)
                   }
                if(charsT.get(c) && charsS.get(c) < charsT.get(c) ){
                    index -= 1
                }
        left++
        }
        right++
    }
 //   console.log("start " + start + " end " + end)
    return s.substring(start,end+1)
};