[LeetCode] Rearrange K Substrings to Form Target String

3365. Rearrange K Substrings to Form Target String

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool isPossibleToRearrange(string s, string t, int k) {
int x = s.length() / k;
string ss = "", tt = "";
unordered_map<string,int> f;
for(int i = 0; i <= s.length(); i++) {
if(i and i % x == 0) {
f[ss]++, f[tt]--;
ss = tt = "";
}
if(i < s.length()) {
ss.push_back(s[i]);
tt.push_back(t[i]);
}
}
for(auto& [_,c] : f) if(c) return false;
return true;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2024/11/24/PS/LeetCode/rearrange-k-substrings-to-form-target-string/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.