Rearrange Characters to Make Target String

Difficulty: Easy | Acceptance: 61.20% | Paid: No Topics: Hash Table, String, Counting

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.

• Examples
• Constraints
• Hash Map / Counter Approach
• Array Counting Approach

Examples

Example 1:

Input: s = "ilovecodingonleetcode", target = "code"
Output: 2
Explanation:
- "code" can be formed using characters from s twice.
- We can take the characters 'c', 'o', 'd', 'e' from s to form the first copy of "code".
- We can take the characters 'c', 'o', 'd', 'e' from s to form the second copy of "code".
- We cannot form a third copy of "code" because we only have one 'e' left.

Example 2:

Input: s = "abcba", target = "abc"
Output: 1
Explanation:
- "abc" can be formed using characters from s once.
- We can take the characters 'a', 'b', 'c' from s to form the first copy of "abc".
- We cannot form a second copy of "abc" because we only have one 'a' left.

Example 3:

Input: s = "abbaccaddaeea", target = "aaaaa"
Output: 1
Explanation:
- "aaaaa" can be formed using characters from s once.
- We can take the characters 'a', 'a', 'a', 'a', 'a' from s to form the first copy of "aaaaa".
- We cannot form a second copy of "aaaaa" because we only have two 'a's left.

Constraints

1 <= s.length <= 100
1 <= target.length <= 10
s and target consist of lowercase English letters.

Hash Map / Counter Approach

Intuition Count the frequency of each character in both strings, then find the limiting character that determines how many copies of target can be formed.

Steps

• Count the frequency of each character in string s using a hash map
• Count the frequency of each character in string target using a hash map
• For each character in target, calculate how many times we can form it using characters from s
• The answer is the minimum of these ratios across all characters in target

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        from collections import Counter
        
        s_count = Counter(s)
        target_count = Counter(target)
        
        result = float('inf')
        
        for char in target_count:
            if char not in s_count:
                return 0
            result = min(result, s_count[char] // target_count[char])
        
        return result

Complexity

• Time: O(n + m) where n is the length of s and m is the length of target
• Space: O(k) where k is the number of unique characters (at most 26 for lowercase letters)
• Notes: Hash map approach is flexible and works for any character set, but has slightly higher overhead than array-based approach.

Array Counting Approach

Intuition Since we only deal with lowercase English letters, we can use fixed-size arrays of length 26 instead of hash maps for better performance.

Steps

• Create two arrays of size 26 to count character frequencies
• Count characters in s by mapping each character to index 0-25
• Count characters in target using the same mapping
• Find the minimum ratio of available to required characters for each character in target

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        s_count = [0] * 26
        target_count = [0] * 26
        
        for c in s:
            s_count[ord(c) - ord('a')] += 1
        
        for c in target:
            target_count[ord(c) - ord('a')] += 1
        
        result = float('inf')
        
        for i in range(26):
            if target_count[i] > 0:
                if s_count[i] == 0:
                    return 0
                result = min(result, s_count[i] // target_count[i])
        
        return result

Complexity

• Time: O(n + m) where n is the length of s and m is the length of target
• Space: O(1) since we use fixed-size arrays of 26 elements
• Notes: This is the most efficient approach for lowercase English letters, with constant space and direct array access.