Rearrange Characters to Make Target String

Easy
1022.

Rearrange Characters to Make Target String

Rearrange Characters to Make Target String is an easy coding problem on strings, hash table and counting, asked in Amazon, Google and TCS interviews.

You may take characters out of s — each one at most once — and rearrange them to spell copies of target.

Return the maximum number of copies of target you can form.

Example 1

Input
s = "codekairocodekairo", target = "code"
Output
2
Explanation
Two `c`s, four `o`s, two `d`s and two `e`s — the `c`, `d` and `e` counts cap it at 2.

Example 2

Input
s = "abcba", target = "abc"
Output
1
Explanation
Only one `c` is available.

Example 3

Input
s = "abbaccaddaeea", target = "aaaaa"
Output
1
Explanation
Five `a`s make exactly one copy.

Constraints

  • 1 <= s.length <= 100
  • 1 <= target.length <= 10
  • s and target consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} target
 * @return {number}
 */
var rearrangeCharacters = function(s, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rearrange Characters to Make Target String — Solution

Rearrange Characters to Make Target String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Rearrange Characters to Make Target String is an easy coding problem on strings, hash table and counting, asked in Amazon, Google and TCS interviews.

  • Difficulty: Easy
  • Topics: Strings, Hash Table, Counting
  • Asked at: Amazon, Google, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may take characters out of s — each one at most once — and rearrange them to spell copies of target.

Return the maximum number of copies of target you can form.

Example 1

Input: s = "codekairocodekairo", target = "code"
Output: 2
Explanation: Two `c`s, four `o`s, two `d`s and two `e`s — the `c`, `d` and `e` counts cap it at 2.

Example 2

Input: s = "abcba", target = "abc"
Output: 1
Explanation: Only one `c` is available.

Example 3

Input: s = "abbaccaddaeea", target = "aaaaa"
Output: 1
Explanation: Five `a`s make exactly one copy.

Constraints

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

Hints for Rearrange Characters to Make Target String

  1. Hint 1

    Count the letters of both strings.

  2. Hint 2

    For each letter the target needs, have / need copies are possible as far as that letter is concerned.

  3. Hint 3

    The answer is the smallest of those per-letter limits.

How to solve Rearrange Characters to Make Target String

Tally both strings, then for each letter the target actually uses, divide the supply by the demand. The bottleneck letter — the smallest quotient — is the answer.

Approach

  1. Count the 26 letters in s and in target.
  2. For each letter with a non-zero demand, compute have / need with integer division.
  3. Return the minimum of those quotients.

Why it works

Integer division is exactly right here: a partial copy is worth nothing, so the floor is the number of whole copies that letter can support. Letters the target never uses are skipped — dividing by a zero demand is both undefined and meaningless.

Complexity

  • Time — O(n + m)
  • Space — O(1) — two 26-slot tallies

Pitfalls

  • Skip letters with zero demand, or you divide by zero.
  • The answer is the minimum across letters, not the sum or the maximum.
  • A letter the target needs but s lacks makes the answer 0.

Reference solution

Python

def rearrangeCharacters(s: str, target: str) -> int:
    have = [0] * 26
    need = [0] * 26
    for c in s:
        have[ord(c) - 97] += 1
    for c in target:
        need[ord(c) - 97] += 1
    return min(have[i] // need[i] for i in range(26) if need[i] > 0)

Java

public static int rearrangeCharacters(String s, String target) {
    int[] have = new int[26];
    int[] need = new int[26];
    for (int i = 0; i < s.length(); i++) have[s.charAt(i) - 'a']++;
    for (int i = 0; i < target.length(); i++) need[target.charAt(i) - 'a']++;
    int best = Integer.MAX_VALUE;
    for (int i = 0; i < 26; i++) {
        if (need[i] == 0) continue;
        best = Math.min(best, have[i] / need[i]);
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

C++

int rearrangeCharacters(string s, string target) {
    vector<int> have(26, 0), need(26, 0);
    for (char c : s) have[c - 'a']++;
    for (char c : target) need[c - 'a']++;
    int best = INT_MAX;
    for (int i = 0; i < 26; i++) {
        if (need[i] == 0) continue;
        best = min(best, have[i] / need[i]);
    }
    return best == INT_MAX ? 0 : best;
}

JavaScript

var rearrangeCharacters = function(s, target) {
    var have = [], need = [], i;
    for (i = 0; i < 26; i++) { have.push(0); need.push(0); }
    for (i = 0; i < s.length; i++) have[s.charCodeAt(i) - 97]++;
    for (i = 0; i < target.length; i++) need[target.charCodeAt(i) - 97]++;
    var best = -1;
    for (i = 0; i < 26; i++) {
        if (need[i] === 0) continue;
        var copies = Math.floor(have[i] / need[i]);
        if (best === -1 || copies < best) best = copies;
    }
    return best === -1 ? 0 : best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets