LeetCode 3365: Rearrange K Substrings to Form Target String Solution

Master LeetCode problem 3365 (Rearrange K Substrings to Form Target String), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3365. Rearrange K Substrings to Form Target String

Medium

Hash Table String Sorting

Problem Explanation

Explanation

To solve this problem, we can follow these steps:

Check if the strings s and t are anagrams of each other. If they are not, return false.
Calculate the frequency of each character in both strings.
For each character c in the strings, the count of c in s should be divisible by k. If not, return false.
Try to form substrings of length len(s) / k from s.
For each substring, check if the characters in the substring match the characters in t based on frequency.
If all substrings can be rearranged to form t, return true. Otherwise, return false.

Time complexity: O(n), where n is the length of strings s and t. Space complexity: O(1).

Solution Code

public boolean canRearrange(String s, String t, int k) {
    if (!isAnagram(s, t)) {
        return false;
    }

    int[] freqS = new int[26];
    int[] freqT = new int[26];

    for (char c : s.toCharArray()) {
        freqS[c - 'a']++;
    }

    for (char c : t.toCharArray()) {
        freqT[c - 'a']++;
    }

    for (int i = 0; i < 26; i++) {
        if (freqS[i] % k != 0) {
            return false;
        }
    }

    return true;
}

private boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int[] count = new int[26];

    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }

    for (char c : t.toCharArray()) {
        count[c - 'a']--;
        if (count[c - 'a'] < 0) {
            return false;
        }
    }

    return true;
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3365 (Rearrange K Substrings to Form Target String)?

This page provides optimized solutions for LeetCode problem 3365 (Rearrange K Substrings to Form Target String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3365 (Rearrange K Substrings to Form Target String)?

The time complexity for LeetCode 3365 (Rearrange K Substrings to Form Target String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3365 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3365 in Java, C++, or Python.

Back to LeetCode Solutions