2516. Take K of Each Character From Left and Right / TypeScript

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.

 

Example 1:

Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation: 
Take three characters from the left of s. You now have two 'a' characters, and one 'b' character.
Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters.
A total of 3 + 5 = 8 minutes is needed.
It can be proven that 8 is the minimum number of minutes needed.

Example 2:

Input: s = "a", k = 1
Output: -1
Explanation: It is not possible to take one 'b' or 'c' so return -1.

 

출처 : https://leetcode.com/problems/take-k-of-each-character-from-left-and-right/description/

 

 

function takeCharacters(s: string, k: number): number {
    
    let countA = 0
    let countB = 0
    let countC = 0

    for(let ch of s){
        if(ch=='a') countA++
        if(ch=='b') countB++
        if(ch=='c') countC++
    }

    if(countA<k || countB<k || countC<k) return -1

    let max = 0

    let extraA = countA - k
    let extraB = countB - k
    let extraC = countC - k

    let j = 0

    for(let i=0;i<s.length;i++){
        if(s[i]=='a') extraA--
        if(s[i]=='b') extraB--
        if(s[i]=='c') extraC--

        while(extraA<0 || extraB<0 || extraC<0){
            if(s[j]=='a') extraA++
            if(s[j]=='b') extraB++
            if(s[j]=='c') extraC++

            j++

        }

        max = Math.max(max, i-j+1)


    }

    return s.length - max

    

    

};

 

문자열 s에서 각 문자 'a', 'b', 'c'가 최소 k번 이상 등장하도록 하기 위해 필요한 최소 시간(또는 최소 문자 수)을 계산하는 함수

 

예시 

s = "aabaaaacaabc"
k = 2

 

1. 각 문자의 총 개수 세기

먼저 문자열 s에서 'a', 'b', 'c'의 총 개수를 셈

 

let countA = 0;
let countB = 0;
let countC = 0;

for (let ch of s) {
    if (ch == 'a') countA++;
    if (ch == 'b') countB++;
    if (ch == 'c') countC++;
}

 

 

• 'a'의 개수 (countA): 8개
• 'b'의 개수 (countB): 2개
• 'c'의 개수 (countC): 2개

2. 각 문자의 개수가 k 이상인지 확인

if (countA < k || countB < k || countC < k) return -1;

 

 

모든 문자의 개수가 k 이상이므로 다음 단계로 진행

 

3. 각 문자의 추가 개수 계산

k 이상인 부분을 제외하고 남은 각 문자의 개수를 계산

 

let extraA = countA - k; // 8 - 2 = 6
let extraB = countB - k; // 2 - 2 = 0
let extraC = countC - k; // 2 - 2 = 0

 

• extraA: 6
• extraB: 0
• extraC: 0

4. 투 포인터를 사용하여 최대 길이의 부분 문자열 찾기

부분 문자열을 제거하여 남은 문자열이 각 문자를 최소 k번 포함하도록 함

 

let max = 0;
let j = 0;

for (let i = 0; i < s.length; i++) {
    // 현재 문자의 extra 값을 감소
    if (s[i] == 'a') extraA--;
    if (s[i] == 'b') extraB--;
    if (s[i] == 'c') extraC--;

    // extra 값이 음수가 되면 왼쪽 포인터를 이동하여 균형을 맞춤
    while (extraA < 0 || extraB < 0 || extraC < 0) {
        if (s[j] == 'a') extraA++;
        if (s[j] == 'b') extraB++;
        if (s[j] == 'c') extraC++;
        j++;
    }

    // 최대 길이 갱신
    max = Math.max(max, i - j + 1);
}

 

 

단계별로 자세히 살펴보기:

 

i (인덱스)	s[i]	extraA	extraB	extraC	j (왼쪽 포인터)	max (최대 길이)
0	'a'	5	0	0	0	1
1	'a'	4	0	0	0	2
2	'b'	4	-1	0	3	2
3	'a'	3	0	0	3	2
4	'a'	2	0	0	3	2
5	'a'	1	0	0	3	3
6	'a'	0	0	0	3	4
7	'c'	0	0	-1	8	4
8	'a'	-1	0	0	9	4
9	'a'	-2	0	0	10	4
10	'b'	-2	-1	0	11	4
11	'c'	-2	-1	-1	12	4

• i = 2에서 extraB가 음수가 되어 j를 증가시키며 균형을 맞춤
• i = 7에서 extraC가 음수가 되어 j를 증가
• i = 8부터 extraA가 음수가 되지만, j를 증가시켜도 extraA가 0 이상이 되지 않음.
• 마지막까지 최대 길이 max는 4로 유지

5. 결과 계산

return s.length - max; // 12 - 4 = 8