Longest Substring With At Most Two Distinct

Given a string s, find the length of the longest substring t that contains at most 2 distinct characters. 최대 2개의 구분되 철자를 포함하는 가장 긴 substring의 길이를 구해라.

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.

자료구조 : 정수형 변수 4개, Map(Character, Integer) 1. start : 시작 인덱스 2. end : 끝 인덱스 3. count : 문자열의 갯수 4. leng : 문자열의 길이(end-start 중 큰 값)

알고리즘 1. Map에 저장한다. - c 2개, a 2개, b 4개 => (c,2) (a,2) (b,4) 2. 문자의 갯수는 최대 2개이다. - 문자 갯수(count)가 2개 넘는다면 start(시작 인덱스)로 이를 제어한다.

알고리즘을 Java로 구현

package java_basic;
import java.util.*;

public class LongestSubMostTwo {

	public static void main(String[] args) {
		String s = "ccaabbb";
		System.out.println(solve(s));
	}

	private static int solve(String s) {
		//1. 그릇 생성 
		Map<Character, Integer> map = new HashMap<>();//(c,2) (a,2) (b,3)
		int start = 0, end = 0, count = 0, leng = 0;
		
		//2. 반복문 돌린다.
		while(end < s.length()) {
			char c = s.charAt(end);
			map.put(c, map.getOrDefault(c, 0)+1);//(c,2) (a,2)
			if(map.get(c) == 1) count++;//new char, count는 2가 된다. 
			end++;
			
			while(count > 2) {//문자 갯수가 2보다 많으면! 
				char tmp = s.charAt(start);
				map.put(tmp,map.get(tmp)-1);
				if(map.get(tmp) == 0) { 
					count--;
				}
				start++;
			}
			//3. leng 리턴
			leng = Math.max(leng, end-start);
		}
		return leng;
		
	}

}

배운 내용 정리(Java 문법 및 메소드) 1. Map.getOrDefault() : 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드

getOrDefault(Object key, V DefaultValue)

char c = s.charAt(end);
map.put(c, map.getOrDefault(c, 0)+1);
//처음에는 c가 map에 없으니 0을 리턴.
//=>map.put(c,1)
//map에 (c,1)이 존재하니까 해당 값인 1을 리턴!
//=>map.put(c,1+1)=>map.put(c,2)