[LeetCode- Ch4. 투 포인터] 2. 최대 2개의 고유 문자가있는 가장 긴 부분 문자열 ##

https://www.lintcode.com/problem/928/description

LintCode 炼码

 

1. 배열을 이용한 풀이

2. Map을 이용한 풀이

 

1. 배열을 이용한 풀이

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
		int[] map = new int[128];
		int left = 0, right = 0, maxLen = 0, counter = 0;

		while (right < s.length()) {
			char c1 = s.charAt(right);

			if (map[c1] == 0)
				counter++;
			map[c1]++;
			right++;

			while (counter > 2) {
				char c2 = s.charAt(left);
				if (map[c2] == 1)
					counter--;
				map[c2]--;
				left++;
			}

			maxLen = Math.max(maxLen, right - left);
		}

		return maxLen;
	}
}

 

2. Map을 이용한 풀이

 

(1) rt를 이용해 문자열 길이까지 ++하면서 돈다.

(2) 2개 이상인 개수 체크

(3) 2개 이상인 문자를 없앤다. -> put으로 개수를 -1씩 하고, 0개가 되면 key값을 없애야 개수를 구할 수 있다.

 

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
 	// 1
		Map<Character, Integer> map = new HashMap<>();
		int l = 0, r = 0, max = 0, counter = 0;

		// 2
		while (r < s.length()) {
			char c = s.charAt(r);
//			System.out.println("c: " + c);
			map.put(c, map.getOrDefault(c, 0) + 1);// c=2, a=2, b=3
			if (map.get(c) == 1)
				counter++;
			r++;
			// 3
			while (counter > 2) {
				char c2 = s.charAt(l);
				map.put(c2, map.get(c2) - 1);
				if (map.get(c2) == 0)
					counter--;
				l++;
			}
			max = Math.max(max, r - l);
			System.out.println("right " + r + " - left " + l + " :" + (r - l));
		}
		return max;
	}
}

 

public class Solution {
    
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        //map의 키가 2개까지 가능
        Map<Character, Integer> map = new HashMap<>();
        int lt=0, rt=0, max=0, cnt=0;

        while(rt<s.length()){
            char c=s.charAt(rt);
            map.put(c, map.getOrDefault(c,0)+1);
            if(map.size()>2){
                cnt++;
            }
            rt++;
            while(cnt>0){
                char c2=s.charAt(lt);
                if(map.size()>2) cnt--;
                map.put(c2,map.get(c2)-1);
                if(map.get(c2)==0)
                map.remove(c2);
                
                lt++;
            }
            int tmp=0;
            for(int x: map.values()) tmp+=x;
            
            max=Math.max(max,tmp);
        }
        return max;
    }
}

 

2가지 고유문자를 유지하는 두가지 방법

(1)  map의 사이즈를 기준으로 분류

while(rt<s.length()){
    char c=s.charAt(rt);
    map.put(c, map.getOrDefault(c,0)+1);
    if(map.size()>2){
        cnt++;
    }
    rt++;
    while(cnt>0){
        char c2=s.charAt(lt);
        if(map.size()>2) cnt--;
        map.put(c2,map.get(c2)-1);
        if(map.get(c2)==0)
        map.remove(c2);

        lt++;
    }
    int tmp=0;
    for(int x: map.values()) tmp+=x;

    max=Math.max(max,tmp);
}

(2) map이 가지고 있는 해당문자의 개수를 기준으로 분류

while (r < s.length()) {
    char c = s.charAt(r);
//			System.out.println("c: " + c);
    map.put(c, map.getOrDefault(c, 0) + 1);// c=2, a=2, b=3
    if (map.get(c) == 1)
        counter++;
    r++;
    // 3
    while (counter > 2) {
        char c2 = s.charAt(l);
        map.put(c2, map.get(c2) - 1);
        if (map.get(c2) == 0)
            counter--;
        l++;
    }
    max = Math.max(max, r - l);
    System.out.println("right " + r + " - left " + l + " :" + (r - l));
}

 

세는 두가지 방법 

(1) map.values()를 이용해 하나씩 모두 세기

int tmp=0;
for(int x: map.values()) tmp+=x;

max=Math.max(max,tmp);

(2) rt-lt를 이용해 한번에 세기

 

max = Math.max(max, r - l);

---