Teaching Kids Programming – Rearrange Characters to Make Target String (Hash Map)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Example 1:
Input: s = “ilovecodingonleetcode”, target = “code”
Output: 2
Explanation:
For the first copy of “code”, take the letters at indices 4, 5, 6, and 7.
For the second copy of “code”, take the letters at indices 17, 18, 19, and 20.
The strings that are formed are “ecod” and “code” which can both be rearranged into “code”.
We can make at most two copies of “code”, so we return 2.

Example 2:
Input: s = “abcba”, target = “abc”
Output: 1
Explanation:
We can make one copy of “abc” by taking the letters at indices 0, 1, and 2.
We can make at most one copy of “abc”, so we return 1.
Note that while there is an extra ‘a’ and ‘b’ at indices 3 and 4, we cannot reuse the letter ‘c’ at index 2, so we cannot make a second copy of “abc”.

Example 3:
Input: s = “abbaccaddaeea”, target = “aaaaa”
Output: 1
Explanation:
We can make one copy of “aaaaa” by taking the letters at indices 0, 3, 6, 9, and 12.
We can make at most one copy of “aaaaa”, so we return 1.

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

Hints:
Count the frequency of each character in s and target.
Consider each letter one at a time. If there are x occurrences of a letter in s and y occurrences of the same letter in target, how many copies of this letter can we make?
We can make floor(x / y) copies of the letter.

Algorithms to Rearrange Characters to Make Target String

The most intuitive solution (bruteforce algorithm) is to go through the letters in target, and remove them if we can from the source. We don’t need to actually remove it coz the string operation is expensive. We can use a Counter aka hash map to count the frequencies of the source string, and then decrement the corresponding value while we simulate the deletion. If we don’t have enough characters in source string (the counter falls negative), we return the current complete scans (copies).

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        S = Counter(s)
        ans = 0
        while True:
            for i in target:
                if S[i] > 0:
                    S[i] -= 1
                else:
                    return ans
            ans += 1
        return 0

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        S = Counter(s)
        ans = 0
        while True:
            for i in target:
                if S[i] > 0:
                    S[i] -= 1
                else:
                    return ans
            ans += 1
        return 0

The time complexity is O(S/T), the space complexity is O(S).

ALternatively, we can use two hash maps (Counter object in Python) to count the number of characters in both string, and the number of copies is determined by the smallest S[i]//T[i aka the flooring value of S[i]/T[i].

1
2
3
4
5
6
7
8

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        T = Counter(target)
        S = Counter(s)
        ans = math.inf
        for i in T:
            ans = min(ans, S[i]//T[i])
        return ans if ans != math.inf else 0

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        T = Counter(target)
        S = Counter(s)
        ans = math.inf
        for i in T:
            ans = min(ans, S[i]//T[i])
        return ans if ans != math.inf else 0

Here is a shorter implemention of the min function that takes the iterator.

1
2
3
4
5

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        T = Counter(target)
        S = Counter(s)
        return min((S[i]//T[i] for i in T), default=0)

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        T = Counter(target)
        S = Counter(s)
        return min((S[i]//T[i] for i in T), default=0)

The time/space complexity is O(S+T).

–EOF (The Ultimate Computing & Technology Blog) —