Leetcode - 159. Longest Substring with At Most Two Distinct Characters

문제

문자열이 주어질때, 최대 2개로만 구성된 가장 긴 substring 길이를 리턴하라.

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

아이디어

• two pointer & sliding window (with hashtable)
  • hashtable빈도수가 2개 이하일때 -> right 증가
  • hashtable빈도수가 2개 초과일때 -> left증가
• two pointer 문제는 어떤 조건에서 right를 증가 시킬지, 그리고 어떤 조건에서 left를 증가시킬지를 먼서 생각해보는 전략을 사용하기.

해결 O(n)

O(n) 이지만 빈도수를 체크할때 매번 hashtable 전체를 순회해야해서 비효율적인 방법. (Runtime: 426 ms)

#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))

int check_nr_char(int *table)
{
    int cnt = 0;
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (table[i] != 0)
            cnt++;
    }
    return cnt;
}

int lengthOfLongestSubstringTwoDistinct(char * s){
    int table[TABLE_SIZE] = {0,};
    int maxlen = 0;
    int ssize = strlen(s);
    int left = 0, right = 0;
   
    table[s[right]]++;
    while (right < ssize) {
        if (check_nr_char(table) <= 2) {
            maxlen = max(maxlen, right - left + 1);
            right++;
            table[s[right]]++;
        }  else {
            table[s[left++]]--;
        }
        
    }
    return maxlen;
}

해결 O(n)

빈도수를 체크할때 hashtable 크기만큼 순회하지 않고, 문자종류 갯수 cur_freq 변수값 하나를 조정해서 수행. 훨씬 효율적이고 빠르다. (Runtime: 22 ms, faster than 80.95%)

hashtable빈도수를 저장할때 0이었다면 총 문자종류개수를 +1 하고, 빈도수를 감소시킬때 0이 된다면 총 문자종류수를 -1 한다.

#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))

int lengthOfLongestSubstringTwoDistinct(char * s){
    int table[TABLE_SIZE] = {0,};
    int maxlen = 0;
    int ssize = strlen(s);
    int left = 0, right = 0;
    int cur_freq = 1;
   
    table[s[right]]++;
    while (right < ssize) {
        if (cur_freq <= 2) {
            maxlen = max(maxlen, right - left + 1);
            right++;
            if (table[s[right]] == 0)
                cur_freq++;
            table[s[right]]++;
        }  else {
            if (table[s[left]] == 1)
                cur_freq--;
            table[s[left++]]--;
        }
        
    }
    return maxlen;
}

해결 O(n)

위와 동일한 로직인데 아래 코드가 더 논리적으로 이해하기 쉽고 간결. 속도도 더 빠르게 나왔음.
(Runtime: 12 ms, faster than 100.00%)

#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))

int lengthOfLongestSubstringTwoDistinct(char * s){
    int table[TABLE_SIZE] = {0,};
    int maxlen = 0;
    int ssize = strlen(s);
    int left = 0, right = 0;
    int cur_freq = 0;
   
    while (right < ssize) {
        table[s[right]]++;
        if (table[s[right]] == 1)
            cur_freq++;

        if (cur_freq <= 2) {
            maxlen = max(maxlen, right - left + 1);
        } else {
            table[s[left]]--;
            if (table[s[left]] == 0)
                cur_freq--;
            left++;
        }
        right++;
        
    }
    return maxlen;
}