Watch 10 video solutions for Rearrange K Substrings to Form Target String, a medium level problem involving Hash Table, String, Sorting. This walkthrough by NeetCode has 57,559 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Input: s = "abcd", t = "cdab", k = 2
Output: true
Explanation:
s into 2 substrings of length 2: ["ab", "cd"].["cd", "ab"], and then concatenating them results in "cdab", which matches t.Example 2:
Input: s = "aabbcc", t = "bbaacc", k = 3
Output: true
Explanation:
s into 3 substrings of length 2: ["aa", "bb", "cc"].["bb", "aa", "cc"], and then concatenating them results in "bbaacc", which matches t.Example 3:
Input: s = "aabbcc", t = "bbaacc", k = 2
Output: false
Explanation:
s into 2 substrings of length 3: ["aab", "bcc"].t = "bbaacc", so the output is false.
Constraints:
1 <= s.length == t.length <= 2 * 1051 <= k <= s.lengths.length is divisible by k.s and t consist only of lowercase English letters.s and t are anagrams of each other.