2516. Take K of Each Character From Left and Right

2516. Take K of Each Character From Left and Right

You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

---

'a', 'b', 'c' 로 이뤄진 sequence 에서 k 개 만큼의 갯수를 얻는 최소 분 ( minutes ) 를 구합니다.

일분마다 양 끝의 character 를 하나씩 얻을 수 있습니다.

 

먼저, 주어진 sequence 에서 k 개의 'a', 'b', 'c' 가 존재하는 지 검사합니다.

이후 오른쪽 방향에서 k 개의 'a', 'b', 'c' 를 얻는 minutes 를 계산하고 n ( sequence.length ) 의 수 만큼 왼쪽의 element 를 추가하면서 직전에 만족한 right bound 를 n 까지 밀어냅니다.

 

밀어내는 과정에서는 항상 k 개의 elements 가 존재하기에 중간마다 만족하는 최소 minutes 를 갱신합니다.

---

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var takeCharacters = function (s, k) {
    var map = [0, 0, 0];
    function g(c) {
        switch (c) {
            case 'a':
                return 0;
            case 'b':
                return 1;
            case 'c':
                return 2;
        }
    }

    for (var i = 0; i < s.length; i++) {
        var l = g(s[i]);
        map[l] += 1;
    }

    for (var i = 0; i < map.length; i++) {
        if (map[i] < k) return -1;
    }

    var min = s.length;
    var map = [0, 0, 0];
    var right = -1;
    for (var j = s.length; j >= 0; j--) {
        if (j < s.length) {
            var r = g(s[j]);
            map[r] += 1;
        }
        if (map[0] >= k && map[1] >= k && map[2] >= k) {
            min = Math.min((s.length - j), min);
            right = j;
            break;
        }
    }

    for (var i = 0; i < s.length; i++) {
        var l = g(s[i]);
        map[l] += 1;

        while (right < s.length) {
            var r = g(s[right]);
            if (map[r] - 1 >= k) {
                map[r] -= 1;
                right += 1;
            }
            else {
                break;
            }
        }

        if (map[0] >= k && map[1] >= k && map[2] >= k) {
            min = Math.min((i + 1) + (s.length - right), min);
        }
    }

    return min;
};