[SlidingWindow][Medium] 424. Longest Repeating Character Replacement

https://leetcode.com/problems/longest-repeating-character-replacement/description/

 

대문자로 이루어진 문자열을 입력받을 때, k 만큼 이 문자를 다른 문자고 고칠 수 있다. 

이때 구할 수 있는 최대 길이의 sub string의 길이를 찾아라.

 

 

생각보다 복잡한 문제. 

 

우선 특정 구간이 있으면 구간내의 특정 문자의 최대 수가

(구간 길이 - 최대문자수 >= k) 

이어야만 유효한 구간 이라는 것이다. 

따라서 이것을 이용 한다. 

 

최대문자수는 각 단어의 수를 집계하고 그것들의 정렬을 사용한다. 

구간 길이는 right - left + 1 이다. 

 

이때 만족하지 않으면 다시 만족할때 까지 left를 당긴다. 

left 에 해당한 문자수를 줄인다.

이것이 적용된 새로운 구간 길이와 최대문자수를 갱신해서 

이 구간이 유효하도록 다시 만든다. 

 

이것의 최대 길이를 구한다. 

 

단어의 길이는 대문자 알파벳만 있으니, vector<int>를 사용한다. 

정렬은 단어수로 정렬해야 한다. 또한 character에 매칭해야 하므로, 

map<int, set<char>> 를 사용한다. 

 

코드 

int characterReplacement(string s, int k) 
{
    int left = 0, right = 0;
    int maxLen = 0;

    map<int, set<char>> mapBuff;    // cnt, char
    vector<int> vCnt;               // cnt for alphabet.
    vCnt.resize('Z' - 'A' + 1, 0);
    for (; right < s.size(); ++right)
    {
        char cur = s[right];
        //
        int idx = cur - 'A';
        auto iter = mapBuff.find(vCnt[idx]);
        if (iter != mapBuff.end())
        {
            iter->second.erase(cur);
            if(iter->second.size() == 0)
                mapBuff.erase(vCnt[idx]);
        }

        ++vCnt[idx];
        if (mapBuff.find(vCnt[idx]) == mapBuff.end())
            mapBuff[vCnt[idx]] = set<char>{ cur };
        else
            mapBuff[vCnt[idx]].insert(cur);

        // check max cnt in area.
        auto revIter = mapBuff.rbegin();
        int maxCntInArea = revIter->first;
        while (right - left + 1 - maxCntInArea > k)
        {
            cur = s[left];
            idx = cur - 'A';
            auto iter = mapBuff.find(vCnt[idx]);
            iter->second.erase(cur);
            if(iter->second.size() == 0)
                mapBuff.erase(vCnt[idx]);

            --vCnt[idx];
            mapBuff[vCnt[idx]].insert(cur);

            ++left;
            // refresh maxCntInArea.
            revIter = mapBuff.rbegin();
            maxCntInArea = revIter->first;
        }

        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;


}

 

결과

 

더 나은 결과들은 조금 더 간단한 방법으로 풀었다. 이 방식에 대한 고찰 필요.