1156. Swap For Longest Repeated Character Substring

문제)

문자열 text가 주어집니다. 이 문자열에서 두 문자의 위치를 바꿀 수 있습니다.

이때, 같은 문자가 반복되는 가장 긴 부분 문자열의 길이를 반환하세요.

즉, 문자열에서 두 문자를 교환한 후에 동일한 문자가 연속으로 반복되는 가장 긴 부분 문자열을 찾아 그 길이를 반환하는 문제입니다.

 

문제 난이도 : 중

 

소요시간 및 풀이)

슬라이딩 윈도우 알고리즘으로 풀려고 시도했으나 풀지 못하였다.

다른 사람의 코드를 보고 해결하였다.

 

a~z까지의 각 문자를 후보로 설정하고, 슬라이딩 윈도우를 통해 해당 문자가 포함된 가장 긴 부분 문자열을 계산한다.

현재 문자가 ch와 다르면 gap을 증가.
이는 현재 부분 문자열에 포함된 다른 문자의 수를 나타냄.

 

그리고 gap이 1보다 크면, 즉 현재 부분 문자열에 두 개 이상의 ch와 다른 문자가 포함된 경우에는
부분 문자열의 시작 위치(j)에 있는 문자가 ch와 다르면, gap을 감소시킨다.
그런 다음 j를 증가시켜 오른쪽으로 이동한다.

 

(예를 들어 bbaaaabbccbb라는 문자열이 주어졌다고 할 때, 처음 ch 값은 a일 것이고, str[0]은 b이다.

그러므로 gap이 1증가된다.

마찬가지로 str[1]은 b이다. 그러므로 gap 1증가 되고, str[0]=b와 a의 값이 다르기 때문에

gap이 1 감소되고 j를 증가시켜서 시작점을 오른쪽으로 이동시킨다.)

 

count_if를 사용하여 문자열에서 ch와 같은 문자의 수를 계산. res를 갱신.
현재 슬라이딩 윈도우의 길이 i - j와 countCh 중 최소값을 취하여 res를 최대값으로 갱신한다.

 

 

소요 시간 : 못 품

 

정답 코드

class Solution
{
public:
    int maxRepOpt1(string str, int res = 0) 
    {
        for (char ch = 'a'; ch <= 'z'; ++ch)
        {
            int i = 0, j = 0, gap = 0;

            while (i < str.size()) 
            {
                if (str[i] != ch) 
                {
                    gap++;
                }

                i++;

                if (gap > 1)
                {
                    // Check if the character at the start position is not equal to 'ch'
                    if (str[j] != ch)
                    {
                        gap--;
                    }
                    j++;
                }
            }

            int countCh = count_if(begin(str), end(str), [&](char ch1) { return ch1 == ch; });
            res = max(res, min(i - j, countCh));
        }
        return res;
    }
};