2287. Rearrange Characters to Make Target String

Hash Table
String
Counting

TIME

O(|s| + |target|)

SPACE

O(1)

Intuition

Each copy of target consumes a fixed number of each of its letters. So the number of copies we can build is limited by whichever target letter runs out first in s. Count both strings, then take the bottleneck.

Approach

Count the frequency of each character in s and in target.
For each distinct character ch in target, s can support count_s[ch] // count_target[ch] copies.
The answer is the minimum of those ratios over all distinct characters of target.

Complexity

Time: O(|s| + |target|), counting both strings
Space: O(1), fixed-size frequency maps (26 letters)

Edge Cases

A target letter absent from s -> ratio is 0, answer 0
Repeated target letters (e.g. "aaaaa") -> integer division by the per-copy count handles it
s shorter than target -> some ratio is 0
Extra letters in s not in target -> ignored

Code

from collections import Counter


class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        """
        2287. Rearrange Characters to Make Target String
        Time: O(|s| + |target|)
        Space: O(1)
        """
        s_counts = Counter(s)
        target_counts = Counter(target)

        return min(s_counts[ch] // need for ch, need in target_counts.items())

/**
 * 2287. Rearrange Characters to Make Target String
 * Time: O(|s| + |target|)
 * Space: O(1)
 */
class Solution {
    public int rearrangeCharacters(String s, String target) {
        int[] sCount = new int[26];
        int[] targetCount = new int[26];

        for (int i = 0; i < s.length(); i++) {
            sCount[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < target.length(); i++) {
            targetCount[target.charAt(i) - 'a']++;
        }

        int answer = Integer.MAX_VALUE;
        for (int c = 0; c < 26; c++) {
            if (targetCount[c] > 0) {
                answer = Math.min(answer, sCount[c] / targetCount[c]);
            }
        }

        return answer;
    }
}