leetcode 76 java

class Solution {
    public String minWindow(String s, String t) {
        HashMap <Character, Integer> hashMap = new HashMap<>();
        HashMap <Character, Integer> hashMap2 = new HashMap<>();
        String result = "";
        for(char c : t.toCharArray()) {
            hashMap.put(c, hashMap.getOrDefault(c, 0)+1);
        }

        int left = 0;
        int right = 0;

        // t에 문자가 얼마나 포함되어 있는지 카운트 해주는 변수
        int count = 0;

        for(right=0; right<s.length(); right++) { // 우측은 계속 확장
            char c = s.charAt(right);
            // 우측 문자 저장
            hashMap2.put(c, hashMap2.getOrDefault(c, 0)+1);

            // 그 문자가 t에 완전히 다 포함되어 있다면 count ++
            if(hashMap.getOrDefault(c, 0).intValue() == hashMap2.getOrDefault(c, 0).intValue()) {
                count ++;
            }

            // 확장한 문자열이 모두 t에 들어가 있다면
            while(count == hashMap.size()) {
                // 결과 refresh
                if(result.equals("") || result.length() > s.substring(left, right+1).length()) {
                    result = s.substring(left, right+1);
                }

                
                c = s.charAt(left);
                // 좌측 커서 우측으로 이동
                hashMap2.put(c, hashMap2.get(c)-1);
                if(hashMap.getOrDefault(c, 0).intValue() > hashMap2.getOrDefault(c, 0).intValue()) {
                    count --;
                }
                left ++;
            }
        }

        return result;
    }
}

 

 

 

시간 복잡도.

T hashMap 초기화 O(T)

S 좌측, 우측 한번씩 이동 각각 O(S)

따라서 O(2S + T) // 최악의 경우

--> O(S+T) -> O(n) 이라고 볼 수 있다.

 

 

알고리즘 과정.

s = "ADOBECODEBANC", t = "ABC"

 

다음 예시를 보면

left right 는 각각 초기 값 0으로 초기화 후 right 는 우측으로 확장한다.

그럼 A D O B E C 까지 확장하게 되고, 이는 A B C 에 속하기 때문에 결과값을 refresh 한다.

여기서 left 도 우측으로 확장한다.(t에포함되는한 계속)

그럼 여기서 D O B E C 까지 되고 이는 t에 속하지 않기 때문에. left 는 한칸 우측으로 이동하고 끝난다.

 

다음 우측 확장시, 

D O B E C O D E B A 까지 다시 확장된다. 이는 A B C 에 속하지만 최소 문자열이 아니라 값 갱신 하지 않는다.

그 후 left 우측 확장

E C O D E B A 까지 확장한다.

 

다음 우측 확장

E C O D E B A N C

좌측 확장

B A N C

 

이값은 최소열 이기 때문에 갱신되고 끝나게 된다.