Rearrange Characters to Make Target String

Rearrange Characters to Make Target String - Problem

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.

Note: Each character from s can only be used once across all copies of target.

Input & Output

Example 1 — Basic Case

$ Input: s = "ilovecodingonleetcode", target = "code"

› Output: 2

💡 Note: We can form "code" twice: first using c,o,d,e from positions, then using remaining c,o,d,e. Characters c and d each appear twice in s, limiting us to 2 copies.

Example 2 — Limited by One Character

$ Input: s = "abcba", target = "abc"

› Output: 1

💡 Note: s has a:2, b:2, c:1. Target needs a:1, b:1, c:1. Character 'c' appears only once in s, so we can form "abc" only 1 time.

Example 3 — Missing Character

$ Input: s = "abbaccaddaeea", target = "aaaaa"

› Output: 1

💡 Note: s has 5 'a' characters and target needs 5 'a' characters, so we can form "aaaaa" exactly 1 time.

Constraints

1 ≤ s.length ≤ 10⁴
1 ≤ target.length ≤ 10⁴
s and target consist of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Source string s and target pattern to form

Count

Count frequency of each character in both strings

Calculate

Find minimum ratio of available/needed for each character

Key Takeaway

🎯 Key Insight: The character with the smallest available/needed ratio determines the maximum number of target copies possible

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to count character frequencies and find the bottleneck character. Best approach is frequency counting which determines how many copies each character can support. Time: O(n + m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Approach	O(n + m)	O(1)	Count character frequencies and calculate maximum possible copies
Brute Force Character Removal	O(n × m × k)	O(n)	Try to form target strings one by one by removing characters from s

Frequency Count Approach — Algorithm Steps

Step 1: Count frequency of each character in string s
Step 2: Count frequency of each character in target
Step 3: For each unique character in target, calculate copies = freq_s[char] / freq_target[char]
Step 4: Return the minimum of all calculated ratios

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count each character in both strings

Calculate Ratios

For each target character, find available/needed

Find Minimum

The smallest ratio is the answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char* s, char* target) {
    // Count character frequencies using arrays (assuming ASCII)
    int sCount[256] = {0};
    int targetCount[256] = {0};
    
    // Count frequencies
    for (int i = 0; s[i]; i++) {
        sCount[(unsigned char)s[i]]++;
    }
    
    for (int i = 0; target[i]; i++) {
        targetCount[(unsigned char)target[i]]++;
    }
    
    int minCopies = INT_MAX;
    
    // For each character in target, calculate how many copies we can make
    for (int i = 0; i < 256; i++) {
        if (targetCount[i] > 0) {
            int available = sCount[i];
            int needed = targetCount[i];
            int copies = available / needed;
            if (copies < minCopies) {
                minCopies = copies;
            }
        }
    }
    
    return minCopies;
}

int main() {
    char s[1001], target[1001];
    fgets(s, sizeof(s), stdin);
    fgets(target, sizeof(target), stdin);
    s[strcspn(s, "\n")] = 0;
    target[strcspn(target, "\n")] = 0;
    
    int result = solution(s, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through s (length n) and target (length m) to count frequencies

✓ Linear Growth

Space Complexity

O(1)

Hash maps store at most 26 characters (constant space for English alphabet)

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler