algoadvance

Leetcode 2287. Rearrange Characters to Make Target String

Problem Statement

You are given two strings: s and target. You are supposed to rearrange the characters of s to create as many target strings as possible.

Example:

Input: s = "ilovecodingonleetcode", target = "code"
Output: 2
Explanation: You can create two "code" strings from the given string.

Clarifying Questions

  1. Case Sensitivity: Are the strings s and target case-sensitive?
    • Assumption: Yes, they are case-sensitive.
  2. Allowed Characters: Are there any constraints on the type of characters in s and target?
    • Assumption: Both strings can contain only lowercase English letters.
  3. String Length: Are there any constraints on the lengths of s and target?
    • Assumption: Both s and target have a length between 1 and 1000.

Strategy

To determine the number of times we can rearrange the characters of s to create the target string:

  1. Count Frequencies: First, we need to count the frequency of each character in both s and target.
  2. Divide and Conquer: For each character in target, check how many times it can appear given the counts in s.
  3. Determine the Minimum: The minimum number across all required characters will give us the maximum number of target strings that can be formed.

Code

Here’s the implementation in Java:

import java.util.HashMap;

public class RearrangeCharacters {
    public int rearrangeCharacters(String s, String target) {
        // Frequency map for the characters in the string s
        HashMap<Character, Integer> sCount = new HashMap<>();
        for (char ch : s.toCharArray()) {
            sCount.put(ch, sCount.getOrDefault(ch, 0) + 1);
        }
        
        // Frequency map for the characters in the target string
        HashMap<Character, Integer> targetCount = new HashMap<>();
        for (char ch : target.toCharArray()) {
            targetCount.put(ch, targetCount.getOrDefault(ch, 0) + 1);
        }
        
        // Calculate the maximum number of times we can form the target string
        int maxCount = Integer.MAX_VALUE;
        for (char ch : targetCount.keySet()) {
            if (sCount.containsKey(ch)) {
                maxCount = Math.min(maxCount, sCount.get(ch) / targetCount.get(ch));
            } else {
                return 0; // If the character is not in s, we cannot form the target at all
            }
        }
        
        return maxCount;
    }

    public static void main(String[] args) {
        RearrangeCharacters rc = new RearrangeCharacters();
        System.out.println(rc.rearrangeCharacters("ilovecodingonleetcode", "code")); // Output: 2
        System.out.println(rc.rearrangeCharacters("abcba", "abc")); // Output: 1
        System.out.println(rc.rearrangeCharacters("abbaccaddaeea", "aaaaa")); // Output: 1
    }
}

Time Complexity

The time complexity of this solution is O(n + m), where n is the length of the string s and m is the length of the string target. This is because we iterate through each character of s and target only once to build the frequency maps and then process those maps.

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