Premium Algo 100 - Sliding Window

Premium Algo 주제인 Sliding Window 이다.

---

Longest Substring With At Most Two Distinct Characters
link: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/description/

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        map<char,int> hashMap; 
        int answer =  INT_MIN, start = 0, end = 0; 

        while(end < s.length()){
            hashMap[s[end]]++; 
            while(hashMap.size() > 2){
                hashMap[s[start]]--; 
                if(hashMap[s[start]] == 0) hashMap.erase(s[start]); 
                start++; 
            }

            if(hashMap.size() <= 2){
                answer = max(answer, end - start + 1); 
            }
            end++; 
        }

        return answer; 
    }
};

---

Longest Substring with At Most K Distinct Characters
link: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        map<char,int> hashMap; 
        int answer = INT_MIN, start = 0, end = 0; 

        while(end < s.length()){
            hashMap[s[end]]++; 

            while(hashMap.size() > k){
                hashMap[s[start]]--; 
                if(hashMap[s[start]] == 0) hashMap.erase(s[start]); 
                start++; 
            }

            if(hashMap.size() <= k){
                answer = max(answer, end - start + 1); 
            }
            end++; 
        }


        return answer; 
    }
};

---

Max Consecutive Ones II
link: https://leetcode.com/problems/max-consecutive-ones-ii/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int answer = INT_MIN; 
        int start = 0, end = 0; 
        int flip = 1; 
        while(end < nums.size()){
            if(nums[end] == 0 && flip <= 0){
                while(start < nums.size() && flip <= 0){
                    flip += nums[start] == 0 ? 1 : 0; 
                    start++; 
                }
            }

            flip -= nums[end] == 0 ? 1 : 0; 
            answer = max(answer, end - start + 1); 
            end++; 
        }

        return answer; 
    }
};

---

Find K-Length Substrings With No Repeated Characters
link: https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        map<char,int> hashMap; 
        int answer = 0, start = 0, end = 0; 
        
        while(end < s.length()){
            if(hashMap.count(s[end])){
                while(start <= hashMap[s[end]]){
                    hashMap.erase(s[start]); 
                    start++; 
                }
                hashMap[s[end]] = end; 
            } else{
                hashMap[s[end]] = end; 
            }

            if(end - start + 1 == k){
                answer++;
                hashMap.erase(s[start]);  
                start++; 
            }

            end++; 
        }

        return answer; 
    }
};

---

복습 필요한 문제

1. Find K-Length Substring With No Repeated Characters : 예전에 한참 풀어보려다가 결국에는 뭔가 막혀서 답을 보고 참고했던 기억이 있다. 결국 그림을 그려서 확인해보니.. Sliding Window 류의 문제에서는 start 포인터를 옮길시에 꼭 그 Window 안에만 있는 범위를 볼 수 있게 그 밖에 범위는 차근차근 지워줘야 한다. 그래서 함부러 start 포인터를 이동하면 start 포인트 전에 있던 캐릭터도 포함되기 때문에 조심해야 겠다.