Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"abcd" "cdab" 2
"aabbcc" "bbaacc" 3
"aabbcc" "bbaacc" 2
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3365: Rearrange K Substrings to Form Target String
class Solution {
public boolean isPossibleToRearrange(String s, String t, int k) {
Map<String, Integer> cnt = new HashMap<>(k);
int n = s.length();
int m = n / k;
for (int i = 0; i < n; i += m) {
cnt.merge(s.substring(i, i + m), 1, Integer::sum);
cnt.merge(t.substring(i, i + m), -1, Integer::sum);
}
for (int v : cnt.values()) {
if (v != 0) {
return false;
}
}
return true;
}
}
// Accepted solution for LeetCode #3365: Rearrange K Substrings to Form Target String
func isPossibleToRearrange(s string, t string, k int) bool {
n := len(s)
m := n / k
cnt := map[string]int{}
for i := 0; i < n; i += m {
cnt[s[i:i+m]]++
cnt[t[i:i+m]]--
}
for _, v := range cnt {
if v != 0 {
return false
}
}
return true
}
# Accepted solution for LeetCode #3365: Rearrange K Substrings to Form Target String
class Solution:
def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
cnt = Counter()
n = len(s)
m = n // k
for i in range(0, n, m):
cnt[s[i : i + m]] += 1
cnt[t[i : i + m]] -= 1
return all(v == 0 for v in cnt.values())
// Accepted solution for LeetCode #3365: Rearrange K Substrings to Form Target String
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3365: Rearrange K Substrings to Form Target String
// class Solution {
// public boolean isPossibleToRearrange(String s, String t, int k) {
// Map<String, Integer> cnt = new HashMap<>(k);
// int n = s.length();
// int m = n / k;
// for (int i = 0; i < n; i += m) {
// cnt.merge(s.substring(i, i + m), 1, Integer::sum);
// cnt.merge(t.substring(i, i + m), -1, Integer::sum);
// }
// for (int v : cnt.values()) {
// if (v != 0) {
// return false;
// }
// }
// return true;
// }
// }
// Accepted solution for LeetCode #3365: Rearrange K Substrings to Form Target String
function isPossibleToRearrange(s: string, t: string, k: number): boolean {
const cnt: Record<string, number> = {};
const n = s.length;
const m = Math.floor(n / k);
for (let i = 0; i < n; i += m) {
const a = s.slice(i, i + m);
cnt[a] = (cnt[a] || 0) + 1;
const b = t.slice(i, i + m);
cnt[b] = (cnt[b] || 0) - 1;
}
return Object.values(cnt).every(x => x === 0);
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.