2287. Rearrange Characters to Make Target String / TypeScript

You are given two 0-indexed strings s and target. You can take some letters from s and rearrange them to form new strings.

Return the maximum number of copies of target that can be formed by taking letters from s and rearranging them.

 

Example 1:

Input: s = "ilovecodingonleetcode", target = "code"
Output: 2
Explanation:
For the first copy of "code", take the letters at indices 4, 5, 6, and 7.
For the second copy of "code", take the letters at indices 17, 18, 19, and 20.
The strings that are formed are "ecod" and "code" which can both be rearranged into "code".
We can make at most two copies of "code", so we return 2.

Example 2:

Input: s = "abcba", target = "abc"
Output: 1
Explanation:
We can make one copy of "abc" by taking the letters at indices 0, 1, and 2.
We can make at most one copy of "abc", so we return 1.
Note that while there is an extra 'a' and 'b' at indices 3 and 4, we cannot reuse the letter 'c' at index 2, so we cannot make a second copy of "abc".

Example 3:

Input: s = "abbaccaddaeea", target = "aaaaa"
Output: 1
Explanation:
We can make one copy of "aaaaa" by taking the letters at indices 0, 3, 6, 9, and 12.
We can make at most one copy of "aaaaa", so we return 1.

 

출처 : https://leetcode.com/problems/rearrange-characters-to-make-target-string/description/

 

 

풀이

function rearrangeCharacters(s: string, target: string): number {

    let map_target = new Map();
    target.split('').forEach(x=>
    {
        if (!map_target.has(x))
        map_target.set(x,1);
        else
        map_target.set(x, map_target.get(x)+1);
    })

    let map_s = new Map();
    
    s.split('').forEach(x=>
    {
        if (map_target.has(x))
        {
            if (!map_s.has(x))
            map_s.set(x,1);
            else
            map_s.set(x, map_s.get(x)+1)
        }
    });
    let min = s.length;
    for (const [key,value] of map_target)
    {
        if (!map_s.has(key) || map_s.get(key) < value )
        return 0;
        else
        {
            let fl = Math.floor(map_s.get(key)/value) 
            min = ( fl < min ) ? fl : min;
        }
    }
    return min;

};

 

 

EX) s = "ilovecodingonleetcode"  target = "code"

Step 1: target 문자열의 각 문자의 빈도를 계산 (map_target 맵 생성)

먼저 target 문자열인 "code"의 각 문자의 빈도를 계산

 

let map_target = new Map();
target.split('').forEach(x => {
    if (!map_target.has(x))
        map_target.set(x, 1);
    else
        map_target.set(x, map_target.get(x) + 1);
});

 

map_target = { 'c' => 1, 'o' => 1, 'd' => 1, 'e' => 1 }

 

Step 2: s 문자열에서 target에 포함된 문자의 빈도를 계산 (map_s 맵 생성)

s 문자열에서 target 문자열에 포함된 문자의 빈도를 계산

let map_s = new Map();
s.split('').forEach(x => {
    if (map_target.has(x)) {
        if (!map_s.has(x))
            map_s.set(x, 1);
        else
            map_s.set(x, map_s.get(x) + 1);
    }
});

 

map_s = { 'c' => 2, 'o' => 3, 'd' => 2, 'e' => 2 }

 

 

Step 3: target 문자열의 각 문자가 s 문자열에서 충분히 있는지 확인하고, 최소 값을 계산

이제 target 문자열의 각 문자에 대해 s 문자열에서의 빈도를 확인하고, s 문자열에서 target 문자열을 만들 수 있는 최소 횟수를 계산

 

let min = s.length;
for (const [key, value] of map_target) {
    if (!map_s.has(key) || map_s.get(key) < value)
        return 0;
    else {
        let fl = Math.floor(map_s.get(key) / value);
        min = (fl < min) ? fl : min;
    }
}
return min;

 

• 'c': Math.floor(2 / 1) = 2
• 'o': Math.floor(3 / 1) = 3
• 'd': Math.floor(2 / 1) = 2
• 'e': Math.floor(2 / 1) = 2

 

이 중에서 최소값은 2