# Solving Leetcode Interviews in Seconds with AI: Rearrange K Substrings to Form Target String


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "3365" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.  

	# Explanation
	Here's the breakdown of the solution:

*   **Anagram Check is Implicit:** Since `s` and `t` are guaranteed to be anagrams, and the substrings must form `t` after rearrangement, we don't need to explicitly check if `s` and `t` are anagrams. This is inherent in the problem conditions.

*   **Substrings' Anagram Condition:** The core idea is that if `s` can be split into `k` equal-sized substrings and rearranged to form `t`, then each substring of `s` (of length `len(s) // k`) must be an anagram of the corresponding substring that could be formed within `t`. More specifically, we can form k potential substrings by dividing `t` into equal parts. The problem boils down to verifying that the substrings of `s` can rearranged to form each of the equal sized substrings of `t`. Therefore, the substrings of s, when counted, should match the counts of substrings formed by t.

*   **Counting Substrings and Comparing:** We iterate through all possible splits of `s` and compare the frequency of anagram-equivalent substrings in `s` and `t`. We check if `s` and `t` are composed of the same count of each substring anagram.

*   **Runtime Complexity: O(n), Storage Complexity: O(n)**
    where n is the length of the strings `s` and `t`.

	
	# Code
	```python
	from collections import Counter

def solve():
    s = input()
    t = input()
    k = int(input())

    n = len(s)
    sub_len = n // k

    if n % k != 0:
        return False

    s_substrings = []
    for i in range(0, n, sub_len):
        s_substrings.append("".join(sorted(s[i:i + sub_len])))

    t_substrings = []
    for i in range(0, n, sub_len):
        t_substrings.append("".join(sorted(t[i:i + sub_len])))

    s_counts = Counter(s_substrings)
    t_counts = Counter(t_substrings)
    
    return s_counts == t_counts

print(solve())
	```