Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


Input: s = "abcd", t = "cdab", k = 2

Output: true

Explanation:

  * Split `s` into 2 substrings of length 2: `["ab", "cd"]`.
  * Rearranging these substrings as `["cd", "ab"]`, and then concatenating them results in `"cdab"`, which matches `t`.

Example 2

1
2
3
4
5
6
7
8
9


Input: s = "aabbcc", t = "bbaacc", k = 3

Output: true

Explanation:

  * Split `s` into 3 substrings of length 2: `["aa", "bb", "cc"]`.
  * Rearranging these substrings as `["bb", "aa", "cc"]`, and then concatenating them results in `"bbaacc"`, which matches `t`.

Example 3

1
2
3
4
5
6
7
8
9


Input: s = "aabbcc", t = "bbaacc", k = 2

Output: false

Explanation:

  * Split `s` into 2 substrings of length 3: `["aab", "bcc"]`.
  * These substrings cannot be rearranged to form `t = "bbaacc"`, so the output is `false`.

Constraints

  • 1 <= s.length == t.length <= 2 * 10^5
  • 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

Method 1 – Multiset Matching of Substrings

Intuition

Since we can rearrange the k substrings, we only need to check if the multiset of substrings of s (split into k equal parts) matches the multiset of substrings of t (split the same way).

Approach

  1. Split s and t into k equal-length substrings.
  2. Count the frequency of each substring in both s and t.
  3. If the multisets match, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <unordered_map>
class Solution {
public:
    bool canRearrangeSubstrings(string s, string t, int k) {
        int n = s.size(), m = n / k;
        unordered_map<string, int> cnt1, cnt2;
        for (int i = 0; i < n; i += m) cnt1[s.substr(i, m)]++;
        for (int i = 0; i < n; i += m) cnt2[t.substr(i, m)]++;
        return cnt1 == cnt2;
    }
};
1
2
3
4
5
6
7
8
9

func canRearrangeSubstrings(s, t string, k int) bool {
    n, m := len(s), len(s)/k
    cnt1, cnt2 := map[string]int{}, map[string]int{}
    for i := 0; i < n; i += m { cnt1[s[i:i+m]]++ }
    for i := 0; i < n; i += m { cnt2[t[i:i+m]]++ }
    if len(cnt1) != len(cnt2) { return false }
    for k, v := range cnt1 { if cnt2[k] != v { return false } }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import java.util.*;
class Solution {
    public boolean canRearrangeSubstrings(String s, String t, int k) {
        int n = s.length(), m = n / k;
        Map<String, Integer> cnt1 = new HashMap<>(), cnt2 = new HashMap<>();
        for (int i = 0; i < n; i += m) cnt1.merge(s.substring(i, i+m), 1, Integer::sum);
        for (int i = 0; i < n; i += m) cnt2.merge(t.substring(i, i+m), 1, Integer::sum);
        return cnt1.equals(cnt2);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun canRearrangeSubstrings(s: String, t: String, k: Int): Boolean {
        val n = s.length; val m = n / k
        val cnt1 = mutableMapOf<String, Int>()
        val cnt2 = mutableMapOf<String, Int>()
        for (i in 0 until n step m) cnt1[s.substring(i, i+m)] = cnt1.getOrDefault(s.substring(i, i+m), 0) + 1
        for (i in 0 until n step m) cnt2[t.substring(i, i+m)] = cnt2.getOrDefault(t.substring(i, i+m), 0) + 1
        return cnt1 == cnt2
    }
}
1
2
3
4
5
6
7

class Solution:
    def canRearrangeSubstrings(self, s: str, t: str, k: int) -> bool:
        n, m = len(s), len(s) // k
        from collections import Counter
        cnt1 = Counter(s[i:i+m] for i in range(0, n, m))
        cnt2 = Counter(t[i:i+m] for i in range(0, n, m))
        return cnt1 == cnt2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

use std::collections::HashMap;
impl Solution {
    pub fn can_rearrange_substrings(s: String, t: String, k: i32) -> bool {
        let n = s.len();
        let m = n / k as usize;
        let mut cnt1 = HashMap::new();
        let mut cnt2 = HashMap::new();
        for i in (0..n).step_by(m) {
            *cnt1.entry(&s[i..i+m]).or_insert(0) += 1;
            *cnt2.entry(&t[i..i+m]).or_insert(0) += 1;
        }
        cnt1 == cnt2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    canRearrangeSubstrings(s: string, t: string, k: number): boolean {
        const n = s.length, m = n / k;
        const cnt1 = new Map<string, number>(), cnt2 = new Map<string, number>();
        for (let i = 0; i < n; i += m) cnt1.set(s.slice(i, i+m), (cnt1.get(s.slice(i, i+m))||0)+1);
        for (let i = 0; i < n; i += m) cnt2.set(t.slice(i, i+m), (cnt2.get(t.slice(i, i+m))||0)+1);
        if (cnt1.size !== cnt2.size) return false;
        for (const [k, v] of cnt1) if (cnt2.get(k) !== v) return false;
        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s, since we split and count substrings in linear time.
  • 🧺 Space complexity: O(n), for storing the substring counts.