C++LeetCode 구현(159.최대 두 글자 의 최 장 하위 문자열)

[LeetCode]159.Longest Substring with At Most Two Distinct Characters 는 최대 두 글자 의 최 장 하위 문자열 이 있 습 니 다.
Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters.
Example 1:
Input: "eceba"
Output: 3
Explanation: tis "ece" which its length is 3.
Example 2:
Input: "ccaabbb"
Output: 5
Explanation: tis "aabbb" which its length is 5.
이 문 제 는 최대 두 글자 의 가장 긴 문자열 을 구 할 수 있 도록 문자열 을 주 었 다.그러면 먼저 생각 나 는 것 은 HashMap 으로 하 는 것 입 니 다.HashMap 은 모든 문자 의 출현 횟수 를 기록 한 다음 에 HashMap 의 맵 수량 이 두 개 를 초과 할 때 여기 서 하나의 맵 을 삭제 해 야 합 니 다.이때 HashMap 에 e 가 2 개,c 가 1 개 있 습 니 다.이때 b 도 HashMap 에 저장 하면 세 쌍 의 맵 이 있 습 니 다.이때 left 는 0 입 니 다.e 부터 맵 값 을 1 로 줄 입 니 다.이때 e 는 하나 더 있 습 니 다.삭제 하지 않 고 left 는 1 이 증가 합 니 다.이때 HashMap 에는 세 쌍 의 맵 이 있 습 니 다.이때 left 는 1 입 니 다.그러면 c 가 되면 맵 값 이 1 을 줄 입 니 다.이때 e 맵 은 0 입 니 다.e 를 HashMap 에서 삭제 하고 left 는 1 을 증가 한 다음 에 업데이트 결 과 는 i-left+1 입 니 다.이 를 통 해 전체 문자열 을 옮 겨 다 닐 때 까지 유추 합 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int res = 0, left = 0;
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); ++i) {
            ++m[s[i]];
            while (m.size() > 2) {
                if (--m[s[left]] == 0) m.erase(s[left]);
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

우 리 는 HashMap 으로 문자 가 나타 난 개 수 를 매 핑 하 는 것 을 제외 하고 모든 문자 의 최신 좌 표를 매 핑 할 수 있다.예 를 들 어 제목 중의 예 인'eceba'는 첫 번 째 e 를 만 나 좌 표를 0,c 를 만 나 좌 표를 1,두 번 째 e 를 만 났 을 때 좌 표를 2,b 를 만 났 을 때 좌 표를 3 매 핑 하여 현재 HashMap 의 매 핑 수 를 매번 판단 한다.2 보다 크 면 맵 을 삭제 해 야 합 니까?아니면 left=0 시 부터 오른쪽으로 찾 아야 합 니까?모든 문자 가 HashMap 에서 의 맵 값 이 현재 좌표 left 와 같 는 지 확인 해 야 합 니 다.예 를 들 어 첫 번 째 e,HashMap 은 이때 맵 값 이 2 이 고 left 의 0 과 같 지 않 습 니 다.그러면 left 는 1 이 증가 합 니 다.c 를 만 났 을 때 HashMap 에서 c 의 맵 값 은 1 입 니 다.이때 left 와 같 습 니 다.그러면 우 리 는 c 를 삭제 하고 left 는 1 을 추가 한 다음 에 결 과 를 업데이트 합 니 다.이 를 통 해 전체 문자열 을 옮 겨 다 닐 때 까지 유추 합 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int res = 0, left = 0;
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); ++i) {
            m[s[i]] = i;
            while (m.size() > 2) {
                if (m[s[left]] == left) m.erase(s[left]);
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

나중에 인터넷 에서 해법 을 보 았 습 니 다.이런 해법 은 sliding window 를 유지 하 는 것 입 니 다.포인터 left 는 시작 위 치 를 가리 키 고 right 는 window 의 마지막 위 치 를 가리 키 며 left 의 다음 점프 위 치 를 찾 는 데 사 용 됩 니 다.생각 은 다음 과 같 습 니 다.
1.현재 문자 가 이전 문자 와 같 으 면 계속 순환 합 니 다.
2.다 르 면 현재 문자 와 right 가 가리 키 는 문자 가 같 는 지 확인 합 니 다.
    (1)똑 같 으 면 left 가 변 하지 않 고 오른쪽 에서 i-1 로 뛰 기
    (2)다 르 면 업데이트 결과,left 는 right+1,right 는 i-1 로 변경
마지막 으로 순환 이 끝 난 후에 결과 res 와 s.size()-left 의 크기 를 비교 하고 큰 것 으로 돌아 가 야 합 니 다.이것 은 문자열 이'ecebaaa'라면 left=3 시,i=5,6 시 에 계속 순환 하고 i 가 7 까지 추 가 했 을 때 순환 을 뛰 어 넘 었 기 때 문 입 니 다.이때 정 답 은'baaa'라 는 네 글자 입 니 다.그리고 우리 의 결과 res 는'ece'라 는 세 글자 만 업데이트 되 었 기 때문에 마지막 으로 s.size()-left 와 결과 res 의 크기 를 판단 해 야 합 니 다.
또한 이 해법 은 서로 다른 문자 수가 2 개 인 경우 에 만 적용 되 며,k 개 라면 위의 두 가지 해법 을 사용 해 야 한 다 는 것 을 설명 해 야 한다.
해법 3:

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int left = 0, right = -1, res = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i - 1]) continue;
            if (right >= 0 && s[right] != s[i]) {
                res = max(res, i - left);
                left = right + 1;
            }
            right = i - 1;
        }
        return max(s.size() - left, res);
    }
};

HashMap 을 사용 하지 않 는 해법 도 있 습 니 다.  Fruit Into Baskets  이 문 제 를 포럼 에서 보 았 는데 사실은 이 두 문 제 는 배경 설정 을 제외 하고 아무런 차이 가 없고 코드 는 기본적으로 복사 해서 직접 사용 할 수 있다.여 기 는 몇 가지 변 수 를 사용 합 니 다.그 중에서 cur 는 현재 가장 긴 문자열 의 길이 이 고 first 와 second 는 현재 후보 문자열 의 두 개의 서로 다른 문자 이 며 cnctLast 는 second 문자 의 연속 길이 입 니 다.모든 문 자 를 옮 겨 다 닙 니 다.만약 에 만난 문자 가 first 와 second 의 임의의 문자 라면 cur 는 1 을 추가 할 수 있 습 니 다.그렇지 않 으 면 cnctLast 는 1 을 추가 할 수 있 습 니 다.새 문자 라면 기본 값 으로 first 문 자 를 도 태 했 습 니 다.이 때 선택 한 문자열 은 second 문자 와 이 새 문자 로 구성 되 어 있 기 때문에 현재 길 이 는 cnctLast+1 입 니 다.그리고 cnt Last 를 업데이트 합 니 다.현재 문자 가 second 라면 cnt Last 는 1 을 증가 합 니 다.그렇지 않 으 면 모두 1 로 초기 화 됩 니 다.cnt Last 가 집계 한 것 은 second 문자 의 연속 길이 이기 때 문 입 니 다.그리고 현재 문자 가 second 와 같 지 않 으 면 이때 first 대 가 는 second 이 고 second 대 가 는 새 문자 입 니 다.마지막 으로 결과 res 를 cur 로 업데이트 하 는 것 을 잊 지 마 세 요.코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int res = 0, cur = 0, cntLast = 0;
        char first, second;
        for (char c : s) {
            cur = (c == first || c == second) ? cur + 1 : cntLast + 1;
            cntLast = (c == second) ? cntLast + 1 : 1;
            if (c != second) {
                first = second; second = c;
            }
            res = max(res, cur);
        }
        return res;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/159
유사 한 제목:
Fruit Into Baskets
Longest Substring Without Repeating Characters
Sliding Window Maximum
Longest Substring with At Most K Distinct Characters
Subarrays with K Different Integers
참고 자료:
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49759/Share-my-c%2B%2B-solution
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49687/Clean-11-lines-AC-answer-O(1)-space-O(n)-time.
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49682/Simple-O(n)-java-solution-easily-extend-to-k-characters
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49708/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-problem.
C++구현 LeetCode(159.최대 두 글자 의 최 장 자 꼬치)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 최대 두 글자 의 최 장 자 꼬치 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!