Google #1 Longest Substring with At Most Two Distinct Characters

 

Writer: Steven, Lee

Date: 1/23, Wednesday

Purpose: Solving #174 Longest Substring with At Most Two Distinct Characters

Level: Hard

Percentage: 45.6% have solved this problem

Time: it took me 30 minutes :)

Time Complexity: O(n) worst case

Runtime:  2 ms, faster than 91.63% of Java online submissions

*The frequency of the problem that appears in the real interviews is more than 50% in 6 months *

한국어 버전은 밑에 있습니다.

* Caution * Before you read the solution that I used, you need to solve this problem by yourself 

* Description *

Given a string s, find the length of the longest substring t  that contains at most 2 distinct characters.

* Example *

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

* What is the Idea? *

 When I solve various problems, Every time I used to try to find out what the main point is. And then, I used to make the code as O(n) or O(log N) my best for the efficient way. Let's solve the problem step by step. First, In this problem, what should we know? This is what I've found. There are two types related to the longest substring with at most two distinct characters. The first type is the same alphabet can be connected. The second type is the same alphabet can be placed randomly. 

   Here is the example. 

Let's analyze s = "ecceebbbea".  

s[0] 'e' and s[1] 'c' are different. It's the substring with at most two distinct characters so far. length is 2

s[1] 'c' and s[2] 'c' are same. It's still the substring with at most two distinct characters so far. length is 3. 

s[2] 'c' and s[3] 'e' are different. It's still the substring with at most two distinct characters so far. length is 4

s[3] 'e' and s[4] 'e' are same. It's still the substring with at most two distinct characters so far. length is 5

s[4] 'e' and s[5] 'b' are different. There are three distinct characters so we need to do something here. I told you about two rules. One of the rules is the same alphabets of substring can be connected. we should consider a connected case. so Actually, next substring starts from s[3] and the longest length is 5 so far

s[3] 'e' and s[4] 'e' are same. It's the substring with at most two distinct characters so far. length is 2

s[4] 'e' and s[5] 'b' are different. It's still the substring with at most two distinct characters so far. length is 3

s[5] 'b' and s[6] 'b' are same. It's still the substring with at most two distinct characters so far. length is 4

s[6] 'b' and s[7] 'b' are same. It's still the substring with at most two distinct characters so far. length is 5

s[7] 'b' and s[8] 'e' are different. It's still the substring with at most two distinct characters so far. length is 6

s[8] 'e' and s[9] 'a' are different. and It's out of the standard. here we need to find out connected alphabets. so next substring starts from s[8] and the longest length is 6 so far.

Return 6

* Check *
you can check out your answer on this site.

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

(한국어)

* 난이도는 어려움입니다.

* 오직 45.6%만이 이 문제를 풀었습니다.

* 저는 30분 정도가 걸렸습니다. ^^/

* 시간 복잡도는 O(n)입니다. 

* 런타임은 2m로 제출자 91.63%보다 더 효율적입니다.  

 * 6개월 동안 실제 인터뷰에서 50% 이상이 출제가 되었습니다 *

* 주의 *  솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

* 지문 *

s가 주어진다. 이때 최대 2개가 다른 문자를 포함한 가장 긴 부분 문자열 t의 길이를 찾아라.

* 예시 *

Example 1:

Input: "eceba"
Output: 3
Explanation: t는 "ece"로 길이가 3이다.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t는 "aabbb"로 길이가 5이다.

* 아이디어 *

 저는 다양한 문제를 풀 때마다 항상 무엇이 핵심이 찾으려고 노력합니다. 그리고 나서 코드를 효율적인 방법을 위해서 O(n) 또는 O(log N)으로 만들려고 최선을 다합니다. 이 문제를 차근차근 풀어봅시다. 첫 번째로 이 문제이서 우리들이 무엇을 알아야 할까요?? 제가 찾은 핵심은 최대 2가지 문자를 포함한 가장 긴 부분 문자열과 관련한 두 가지 타입이 있는 것입니다. 첫 번째 타입은 같은 알파벳은 연결할 수 있습니다. 두 번째 타입은 같은 알파벳은 랜덤하게 위치할 수 있습니다.

   다음은 예시입니다.

s = "ecceebbea"라는 문자열을 분석해봅시다.

s[0] 'e'와 s[1] 'c'는 다릅니다. 이것은 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 2입니다.

s[1] 'c'와 s[2] 'c'는 같습니다. 이것은 여전히 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 3입니다.

s[2] 'c'와 s[3] 'e'는 다릅니다. 이것은 여전히 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 4입니다.

s[3] 'e'와 s[4] 'e'는 같습니다. 이것은 여전히 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 5입니다.

s[4] 'e'와 s[5] 'b'는 다릅니다. 세 개의 다른 문자들이 있기 때문에 우리는 뭔가를 여기에서 해야 합니다. 규칙들 중 하나인 부분 문자열의 같은 문자들은 연결될 수 있다라는 것을 알면 우리들은 연결된 케이스를 고려해야 합니다. 그래서 사실, 다음 문자열은 s[3]에서부터 시작해야 합니다. 그리고 지금까지 가장 긴 길이는 5입니다. 

s[3] 'e'와 s[4] 'e'는 같습니다. 이것은 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 2입니다.

s[4] 'e'와 s[5] 'b'는 다릅니다. 이것은 여전히 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 3입니다.

s[5] 'b'와 s[6] 'b'는 같습니다. 이것은 여전히 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 4입니다.

s[6] 'b'와 s[7] 'b'는 같습니다. 이것은 여전히 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 5입니다.

s[7] 'b'와 s[8] 'e'는 다릅니다. 이것은 여전히 최대 두 개의 다른 문자를 포함한 문자열입니다. 길이는 6입니다.

s[8] 'e'와 s[9]는 다릅니다. 그리고 이것은 기준에서 벗어났습니다. 여기에서 우리는 연결된 알파벳을 찾습니다. 그리고 다음 문자열은 s[8]에서 시작합니다. 그리고 가장 긴 길이는 6입니다.

6을 반환합니다.

* Check *
이 사이트에서 정답의 유무를 확인하실 수 있습니다.

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

Code & 코드

You need to read the code by yourself

스스로 코드를 읽을 줄 알아야 합니다.

public class LongestSubstringwithAtMostTwoDistinctCharacters_159 {
    public static int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s == null || s.length() == 0) return 0;
        int max = 0, candi = 0, i = 0, chain = 1;
        char[] c = s.toCharArray();
        char first, second;
        
        first = c[0];
        
        for(i = 0 ; i < c.length && c[i] == first; i++) {}
        if(i == c.length) return i;
        
        max = candi = i;
        second = c[i];
        
        for(i = i ; i < c.length ; i++) {
            if(c[i] == first || c[i] == second) candi++;
            else {
                first = c[i-1];
                second = c[i];
                max = Math.max(max, candi);
                candi = chain+1;
            }
            if(c[i] == c[i-1]) chain++;
            else chain = 1;
        }
        
        max = Math.max(max, candi);
        return max;
    }
 
    public static void main(String[] args) {
        int res = lengthOfLongestSubstringTwoDistinct("eceba");
        System.out.println("Result: " + res);
    }
}