문제링크: 76. Minimum Window Substring

---

📖 문제설명

문자열 s, t가 주어졌을 때 t의 모든 문자가 포함(순서 상관 없이)되는 가장 작은 substring을 구하는 문제

💡 접근방식

t에 속한 문자를 관리하는 자료구조가 하나 필요하다 생각

        HashMap<Character,Integer> tMap = new HashMap<Character,Integer>();
        for(char c : t.toCharArray()){
            if(tMap.containsKey(c)){
                tMap.put(c, tMap.get(c)+1);
                continue;
            }
            tMap.put(c,1);
        }

HashMap을 활용하여 t의 문자들을 관리

s를 순회하며 MAP에 속한 key가 탐색 될 경우 그 인덱스를 시작으로 MAP이 빌 때까지 탐색하게 알고리즘을 구현

코드:

class Solution {
    public String minWindow(String s, String t) {
        if(s.length()<t.length()) return "";
        if(s.equals(t)) return s;

        String res = "";

        HashMap<Character,Integer> tMap = new HashMap<Character,Integer>();
        for(char c : t.toCharArray()){
            if(tMap.containsKey(c)){
                tMap.put(c, tMap.get(c)+1);
                continue;
            }
            tMap.put(c,1);
        }
        
        for(int i=0; i<=s.length()-t.length(); i++){
            if(tMap.containsKey(s.charAt(i))){
                HashMap<Character,Integer> cMap = new HashMap<Character, Integer>();
                cMap.putAll(tMap);
                for(int j=i; j<s.length(); j++){
                    if(cMap.containsKey(s.charAt(j))){
                        cMap.put(s.charAt(j), cMap.get(s.charAt(j))-1);
                        if(cMap.get(s.charAt(j))==0) {
                            cMap.remove(s.charAt(j));
                        }
                    }
                    if(cMap.isEmpty()){
                        if(res.equals("")) res = s;
                        String tmp = "";

                        if(j==s.length()-1){
                            tmp = s.substring(i);
                        } else {
                            tmp = s.substring(i,j+1);
                        }

                        if(res.length()>tmp.length()){
                            res = tmp;
                        }
                    }
                }
            }
        }

        return res;
    }
}

하지만 성능이 너무 좋지 않아 Time Limit Exceeded가 뜬다.

📌 개선

코드:

class Solution {
  public String minWindow(String s, String t) {
    int[] count = new int[128];
    int required = t.length();
    int bestLeft = -1;
    int minLength = s.length() + 1;

    for (final char c : t.toCharArray())
      ++count[c];

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (--count[s.charAt(r)] >= 0)
        --required;
      while (required == 0) {
        if (r - l + 1 < minLength) {
          bestLeft = l;
          minLength = r - l + 1;
        }
        if (++count[s.charAt(l++)] > 0)
          ++required;
      }
    }

    return bestLeft == -1 ? "" : s.substring(bestLeft, bestLeft + minLength);
  }
}

MAP자료구조를 사용할 필요 없이 char타입일 경우 아스키코드의 정수로 저장된다는 성질을 활용하면 배열로 정보를 관리할 수 있음

투포인터를 활용해서 l, r을 반환해야하는 배열의 양끝으로 관리하는 것 같음.
그리고 t의 정보를 관리하는 배열이 빌 때 까지 r을 증가 시키고 비어있는 경우에는 l을 증가시키고 required을 증가시켜서 위 과정을 계속해서 반복중