Get started

Rearrange Characters to Make Target String — Easy Problem & Solution

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

  • 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.

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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue