입력

• 문자열 배열 gems
• 1 <= gems.length <= 100,000

출력

• 최단 구간

요구 사항

• O(nlogn) 이하로 해결
• 출력이 ‘구간’
  • 투 포인터

def solution(gems):
    n = len(gems)
    # 보석의 종류를 저장할 set
    kind = len(set(gems))
    
    if kind == 1:
        return [1, 1]
    
    # 포인터 s, e 
    s, e = 0, 0
    # 결과를 저장할 res 배열 
    # 수집된 각 보석의 등장 횟수를 기록할 dic, 첫 보석 추가
    res, dic = [1, n], {gems[0]: 1}
    
    while True:
        
        # 보석의 종류 보다, 수집된 보석의 종류가 작을 경우
        # 아직, 전체 보석 종류가 안 나온 경우
        if len(dic) < kind:
            e += 1
            # 탈출 조건: e가 n보다 크면 모두 검사했다는 의미
            if e >= n:
                break
            dic[gems[e]] = dic.get(gems[e], 0) + 1
        
        # 보석의 종류가 모두 수집되었으면     
        else:
		        # 구간의 길이를 갱신
            if (e-s) < (res[1] - res[0]):
                res = [s+1, e+1]
            
            # s가 1이면 삭제
            if dic[gems[s]] == 1:
                del dic[gems[s]]
            # 아닐 경우, -1
            else:
                dic[gems[s]] -= 1
                
            # 추가적으로 더 좁은 범위도 가능한지 검증    
            s += 1
    
    return res