Rearrange Characters to Make Target String

Problem Summary

• Given input and target strings
• How many copies of target word can be made

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Strings
• Hash Map

Time & Space Complexity

• Time: $O(n+m)$ → Reason: Iterating through both strings once
• Space: $O(1)$ → Reason: Storing counts of 26 chars of the alphabet

Code

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        countActual = {}
        for c in s:
            countActual[c] = countActual.get(c, 0) + 1
        
        countNeeded = {}
        for c in target:
            countNeeded[c] = countNeeded.get(c, 0) + 1

        result = []
        for c in target:
            if c not in countActual:
                return 0
            result.append(countActual[c] // countNeeded[c])
        
        return min(result)