algoadvance

Leetcode 2287. Rearrange Characters to Make Target String

Problem Statement

You are given two strings s and target. You want to rearrange the characters of s to form the string target. You can use each character in s at most once. Return the maximum number of times you can form target from s.

Clarifying Questions

  1. What is the expected input size?
    • Typically, the length of s and target can vary up to 10^4 characters.
  2. Are there any constraints on the characters in s and target?
    • Both s and target will only consist of lowercase English letters.
  3. Should we consider leading or trailing whitespace or casing in the strings?
    • No, we should assume s and target consist only of lowercase English letters without any whitespace.
  4. What should be returned if it is not possible to form target even once?
    • You should return 0.

Strategy

  1. Frequency Calculation:
    • Calculate the frequency of each character in both s and target.
  2. Determine the Maximum Formations:
    • For each character in target, check how many times you can form target based on the character’s frequency in s. The limiting factor will be the character that can be used the fewest number of times.
  3. Divide and Minimize:
    • For every character in target, divide the frequency in s by the required frequency in target and find the minimum value among all these divisions.

Code

Let’s implement this approach in C++:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <climits>

using namespace std;

int rearrangeCharacters(string s, string target) {
    // Create frequency maps for s and target
    unordered_map<char, int> freqS;
    unordered_map<char, int> freqTarget;
    
    // Fill the frequency maps
    for (char c : s) {
        freqS[c]++;
    }
    
    for (char c : target) {
        freqTarget[c]++;
    }
    
    // Initialize the minimum number of target we can form
    int minCount = INT_MAX;
    
    // Compute the maximum number of times we can form target
    for (auto& [charT, countT] : freqTarget) {
        // If s does not contain charT, we cannot form the target at all
        if (freqS.find(charT) == freqS.end()) {
            return 0;
        }
        
        // Calculate the number of times we can use charT
        minCount = min(minCount, freqS[charT] / countT);
    }

    return minCount;
}

// Example usage:
int main() {
    string s = "ilovecodingonleetcode";
    string target = "code";
    
    int result = rearrangeCharacters(s, target);
    cout << "Maximum number of times we can form the target: " << result << endl;
    
    return 0;
}

Time Complexity

This solution efficiently calculates the maximum number of times you can form the target target from string s.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI