Skip to content

3365. Rearrange K Substrings to Form Target String 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  bool isPossibleToRearrange(string s, string t, int k) {
    const int n = s.length();
    return getCount(s, n / k) == getCount(t, n / k);
  }

 private:
  unordered_map<string, int> getCount(const string& s, int sz) {
    unordered_map<string, int> count;
    for (int i = 0; i < s.length(); i += sz)
      ++count[s.substr(i, sz)];
    return count;
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public boolean isPossibleToRearrange(String s, String t, int k) {
    final int n = s.length();
    return getCount(s, n / k).equals(getCount(t, n / k));
  }

  private Map<String, Integer> getCount(final String s, int sz) {
    Map<String, Integer> count = new HashMap<>();
    for (int i = 0; i < s.length(); i += sz)
      count.merge(s.substring(i, i + sz), 1, Integer::sum);
    return count;
  }
}

1
2
3
4
5
class Solution:
  def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
    n = len(s)
    return (collections.Counter(s[i:i + n // k] for i in range(0, n, n // k)) ==
            collections.Counter(t[i:i + n // k] for i in range(0, n, n // k)))