꿀잠

https://leetcode.com/problems/longest-repeating-character-replacement/description/

특정 구간의 문자열이 하나로만 이루어져 있을 때 가장 긴 구간을 체크하는 문제이다. 단 k 개의 개수까지 다른 문자를 허용한다.

정답을 구하기 위하여 배열을 이용하여 글자 수가 늘어나는 것을 체크해주었다. 이 때 특정 길이까지 한번 체크한 이후에는 그 길이 이상일 경우만 정답이 될 수 있다는 점을 이용해 길이 조건을 유지할 수 있다. 반복된 문자 개수와 k의 합계가 현재의 길이보다 크다면 left를 증가 시켜 길이를 체크해 주었다. 아래는 전체 통과 코드이다.

public class Solution {  
    public int characterReplacement(String s, int k) {  
        int[] current = new int[26];  
        int maxRepeat = 0;  
        int answer = 0;  
        int l = 0;  
  
        for(int r = 0; r < s.length(); r++){  
            char now = s.charAt(r);  
            current[now - 'A']++;  
            maxRepeat = Math.max(maxRepeat, current[now - 'A']);  
  
            if(r - l + 1 - maxRepeat > k){  
                current[s.charAt(l) - 'A']--;  
                l++;  
            }  
  
            answer = Math.max(r - l + 1, answer);  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/minimum-window-substring/description/

두 문자열이 주어질 때 두번째 문자열이 첫번째 문자열에 모두 포함될 수 있는 최소 길이를 찾는 문제이다.

부분 문자열을 찾기 위해 좌우측 끝을 슬라이딩 하며 찾아주었다. 이 때 문자열이 포함되는지 여부는 Map 자료구조를 이용해 주었다. 중복되는 문자도 있을 수 있으므로 Map의 Key를 문자로 하고 반복 값을 Value로 해주었다.

우측을 증가 시키며 문자열을 확인해 주었으며, 문자열이 확인된 이후에는 좌측을 증가 시켜 문자의 최소 길이를 측정해주었다. 완성된 코드는 아래와 같다.

  
import java.util.*;  
  
public class Solution {  
    public String minWindow(String s, String t) {  
  
        // t의 문자열 정보 저장  
        Map<Character, Integer> chkMap = new HashMap<>();  
        for(char c : t.toCharArray()){  
            chkMap.put(c, chkMap.getOrDefault(c, 0) + 1);  
        }  
  
        // 슬라이딩 되는 문자열 저장  
        Map<Character, Integer> curMap = new HashMap<>();  
  
        // t의 문자열의 총 개수  
        int complete = t.length();  
        // t의 문자열과 현재 슬라이딩 중인 문자열의 개수가 같은 정도  
        int maked = 0;  
        String answer = "";  
  
        // 좌측  
        int l = 0;  
        // 우측을 증가시키며 체크  
        for(int r = 0; r < s.length(); r++){  
            char right = s.charAt(r);  
            // 현재 우측 문자의 포함여부 확인  
            if(chkMap.containsKey(right)){  
                int value = chkMap.get(right);  
                int curValue = curMap.getOrDefault(right, 0) + 1;  
                curMap.put(right, curValue);  
                // 동일 문자가 나오는 경우 필요한 문자인지 체크  
                if(curValue <= value) maked++;  
            }  
  
            // 좌측 문자의 최대값 찾기  
            while(complete == maked){  
                String now = s.substring(l, r + 1);  
                answer = answer.length() == 0 || now.length() < answer.length() ? now : answer;  
  
                char left = s.charAt(l);  
                if(chkMap.containsKey(left)){  
                    int value = chkMap.get(left);  
                    int curValue = curMap.get(left) - 1;  
                    curMap.put(left, curValue);  
                    if(curValue < value) maked--;  
                }  
  
                // 우측이 고정된 상태에서 좌측을 증가시키며 체크  
                l++;  
            }  
        }  
  
        return answer;  
    }  
}