3595. Rearrange K Substrings To Form Target String¶

3595. Rearrange K Substrings to Form Target String

Medium

You are given two strings s and t, both of which are anagrams of each other, and an integer k.

Your task is to determine whether it is possible to split the string s into k equal-sized substrings, rearrange the substrings, and concatenate them in any order to create a new string that matches the given string t.

Return true if this is possible, otherwise, return false.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= s.length == t.length <= 2 * 105
• 1 <= k <= s.length
• s.length is divisible by k.
• s and t consist only of lowercase English letters.
• The input is generated such that s and t are anagrams of each other.

Solution¶

class Solution {
    public boolean isPossibleToRearrange(String s, String t, int k) {
        int n = s.length();
        int part = n / k;
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i += part) {
            String current = s.substring(i, i + part);
            map.put(current, map.getOrDefault(current, 0) + 1);
        }
        for (int i = 0; i < n; i += part) {
            String current = t.substring(i, i + part);
            if (map.getOrDefault(current, 0) > 0) map.put(current, map.getOrDefault(current, 0) -1);
            else return false;
        }
        return true;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]