Rearrange K Substrings to Form Target String
Source: leetcode
Difficulty: Medium
Tags: hash-table, string, sorting

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:**


- 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:**



**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:**



**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 * 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.




C++ solution:
class Solution {
public:
    bool isPossibleToRearrange(string s, string t, int k) {

        int n = s.length();
        int m = t.length();

        if(n % k != 0 || m % k != 0)
            return false;
        
        unordered_map<string, int> mp1;
        unordered_map<string, int> mp2;

         int len = n / k;

        //Storing substrings of s
        for(int i = 0; i < n; i += len){
            string temp = s.substr(i, len);
            mp1[temp]++;
        }

        //Storing substrings of t
        for(int i = 0; i < m; i += len){
            string temp = t.substr(i, len);
            mp2[temp]++;
        }

        return mp1 == mp2;
    }
};

Go solution:
func isPossibleToRearrange(s string, t string, k int) bool {
	var (
		n     = len(s)
		count = make(map[string]int)
	)

	k = n / k

	for i := k - 1; i < n; i += k {
		sub1, sub2 := s[i-k+1:i+1], t[i-k+1:i+1]
		count[sub1]++
		count[sub2]--

		if val, ok := count[sub1]; ok && val == 0 {
			delete(count, sub1)
		}

		if val, ok := count[sub2]; ok && val == 0 {
			delete(count, sub2)
		}
	}

	return len(count) == 0
}

Java solution:
class Solution {
    public boolean isPossibleToRearrange(String s, String t, int k) {
        List<String> l1 = new ArrayList<>();
        List<String> l2 = new ArrayList<>();
        int n = s.length()/k;
        for(int i=0;i<s.length();i=i+n){
            l1.add(s.substring(i,i+n));
            l2.add(t.substring(i,i+n));
        }
        Collections.sort(l1);
        Collections.sort(l2);
        if(l1.equals(l2)){
            return true;
        }
        return false;
    }
}

JavaScript solution:
/**
 * @param {string} s
 * @param {string} t
 * @param {number} k
 * @return {boolean}
 */
var isPossibleToRearrange = function (s, t, totalPairs) {
    if (s.length !== t.length) return false
    let elemPerPairs = Math.floor(s.length / totalPairs)

    let tSplitMap = new Map();
    let sSplitMap = new Map();
    for (let i = 0; i < totalPairs; i++) {
      // to calculate starting and ending indexes for slicing 
        let [start, end] = [i * elemPerPairs, (i * elemPerPairs) + elemPerPairs]
        sSplitMap.set(s.slice(start, end), (sSplitMap.get(s.slice(start, end)) || 0) + 1);
        tSplitMap.set(t.slice(start, end), (tSplitMap.get(t.slice(start, end)) || 0) + 1)
    }
    for (let [key, val] of tSplitMap) {
// return false if key doesn't exist or is not in same frequency
        if (sSplitMap.get(key) !== val) return false;
    }

    return true
};

Python solution:
class Solution:
    def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
        
        n = len(s)
        if k == 1 or k == n: return (s == t)|(k == n)

        m = n // k
        d = defaultdict(int)

        for i in range(0, n, m): 
            d[s[i: i + m]]+= 1

        for i in range(0, n, m):
            tt = t[i: i + m]
            d[tt]-= 1
            if d[tt] < 0: return False
            
        return True

Ruby solution:
def is_possible_to_rearrange(s, t, k)
  n = s.size
  seg_len = n / k
  return s == t if k == 1
  segments_s = []
  segments_t = []
  (0...n).step(seg_len) { |i| 
    segments_s << s[i, seg_len] 
    segments_t << t[i, seg_len] 
  }
  segments_s.tally == segments_t.tally
end