💡 Longest Substring Without Repeating Characters

Given a string s, find the length of the longest
substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Solution

unordered_set<>을 사용해서 이미 사용된 알파벳을 O(1)에 체크할 수 있도록 한다

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<int> set;

        int i = 0;
        int j = 0;

        int longest = 0;

        while (j < s.size()) {
            if (set.find(s[j]) == set.end()) {
                set.insert(s[j]);
                longest = max(longest, j - i + 1);
                j++;
            } else {
                //중복 글자가 있다면 일단 substring은 연속이어야 되기 때문에
                // 첫 글자를 포기할 수 밖에 없다
                set.erase(s[i]);
                i++;
            }
        }

        return longest;
    }
};

💡 Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Constraints:

• 1 <= s.length <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Solution

코드보고도 이해가 잘 안가서
유투브 영상을 본다,,,,

일단 지금 보고 있는 window의 character를 각각 count하기 위해서 array 저장소가 필요
이렇게 수를 세는 이유는 적은 character를 replace 하기 위함이다

이 수를 k와 비교해서 가능한 substring인지 체크 가능하다

.. 여기까지는 코드만 보고서도 이해했었음

maxCount = max(maxCount, alphabet[s[j] - 'A']);
이부분이 left pointer를 오른쪽으로 옮기면서 업데이트를 안하는 부분이 이해가 안됐었는데,,
(왜냐면 left pointer를 오른쪽으로 옮기면 letter을 window에서 하나씩 빼는거라 숫자가 작아지는데, 그럼 maxCount도 다시 지금 count table에서의 maximum으로 업데이트 해야하는게 아닌가...)

하지만!

Result is only going to be maximized as we find a new maxCount
because we want the substring length to be maximized so therefore we also want the maxCount to be maximized
k is CONSTANT!
{substring_length} - maxCount <= k

‼️ 결론은 result(=substring length)가 커지길 기대할 때,
constant인 k 보다 작거나 같다는 조건을 유지하려면
당연히 maxCount도 그에 맞게 커져야 한다

maxCount를 업데이트 한다고 해서 새 max result가 찾아지는게 아니다!!

정리하자면 maxCount가 클떄가 result가 maximize 되었을 때이다

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> alphabet(26);
        int maxCount = 0; //count of the more frequent alphabet in current substring

        int i = 0;
        int j = 0;

        int result = 0;

        while (j < s.size()) {
            alphabet[s[j] - 'A']++;
            maxCount = max(maxCount, alphabet[s[j] - 'A']); 

            if ((j - i + 1) - maxCount > k) {
                // 더 많이 나타나는 알파벳 개수를 빼면 replace 해야할 알파벳의 개수가 계산된다
                // k 보다 크면 불가능 하므로
                alphabet[s[i] - 'A']--;
                i++;

                // ** axCount 업데이트 하지 않아도 된다!!! 
            }

            result = max(result, j - i + 1);
            j++;
        }

        return result;

    }
};

💡 Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window
substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

Solution

1. t의 letter를 map에 기록, t의 letter 개수를 counter에 기록
2. j가 가르키는 letter가 t에 있는 letter라면 map에서 빼주고 counter도 빼준다
3. j가 가르키는 letter가 t에 없는 letter라면 map에서만 빼줌 (마이너스가 되겠지)
   • 핵심은 counter가 0이 되면 map에서t에 있는 letter들은 모두 0, 나머지는 마이너스
4. counter가 0이 된다면 현재 min과 비교해서 더 작은 수를 기록
5. i를 오른쪽으로 옮긴다
   • map의 letter해서 더해준다 (하나가 빠졌으니)
   • 이때 이 값이 0보다 크다면 t의 letter 중에서 하나가 빠졌다는 뜻이기 때문에 counter++
   • i를 옮겨도 counter가 여전히 0이라면 min을 찾기위해 4. 부터 반복한다
6. 2.부터 의 과정을 j가 string 밖으로 벗어나기 전까지 반복한다

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> map;

        // 1. t의 letter를 기록, counter도 기록
        int counter = t.length();
        for (int n = 0; n < counter; n++) {
            map[t[n]]++;
        }

        int i = 0;
        int j = 0;

        int result_start = 0;
        int result_length = INT_MAX;

        while (j < s.length()) {
            // 2. j가 가르키는 letter가 t에 있는 letter이면
            if (map[s[j]] > 0) {
                counter--;
            }

            // 2,3. 사용한 letter는 consume해준다
            //  -> t에 있는 letter는 0으로 갈거고 나머지 letter들은 마이너스가 되는것이 핵심
            map[s[j]]--; 
            j++; //후의 substring 계산 메소드 특성상 미리 더해준다

            while (counter == 0) { //counter가 0인동안은 i를 옮겨주어서 min을 찾도록 한다
                // 일단 현재 min 기록해주고
                if (j - i < result_length) {
                    result_start = i;
                    result_length = j - i;
                }
                
                // i를 옆으로 옮겨도 valid한지 보자
                map[s[i]]++;
                if (map[s[i]] > 0) { //t의 letter중 하나가 window에서 빠졌다는 뜻
                    counter++; //이렇게 되면 현재 while에서 빠져나오고 
                }
                // 위의 if문을 거치지 않았다면 minimum result를 위해 계속 i를 increase한다
                i++;
            }
        }

        if (result_length < INT_MAX) {
            return s.substr(result_start, result_length);
        }
        return "";
    }
};