PROBLEM LINK:
Author: Devendra Aggarwal
Tester: Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Sorting
PROBLEM:
Given two lowercase strings, each of length N, determine if you can transform the first string into the second by swapping letters that are positioned exactly D apart.
QUICK EXPLANATION:
Let s be the first string and t be the second string. Let s_i and t_i be the i th letters of s and t, respectively.
For each i, 1 \le i \le D, check whether the following are the same multisets of letters:
It can be done in O(N/D) by simply counting the letters. If they are the same for all i, then the answer is Yes. Otherwise, it is No.
EXPLANATION:
Let s be the first string and t be the second string. Let s_i and t_i be the i th letters of s and t, respectively.
If we can swap any pair of letters, obviously we can turn s and t, as long as the multiset of letters of s and t are the same. But we can only swap letters that are of distance D apart, and this can be rather restricting. For example, the letter at position 1 can only have the following final positions:
More generally, an letter at position i can only have the final positions i, i + D, i + 2D, \ldots. Not only that, but also i - D, i - 2D, i - 3D, \ldots. in other words, i + kd for integer k.
Another way of stating this is: a letter at position i can have the final position j if and only if i \equiv j \pmod{D} (using congruence notation). Thus, we know that any letters at positions i and j such that i \not\equiv j \pmod{D} will never be able to interact with each other, so we may split s and t into D subsequences, where we can only rearrange elements belonging to the same subsequence. For 1 \le i \le D, let’s define s(i) as the subsequence of s starting from position i and taking every D th letter. Thus:
Define t(i) similarly. Now, we can only swap consecutive letters belonging to the same subsequence, and for each i, only s(i)'s letters can be used to form t(i). Thus, we have the following necessary condition for being able to transform s to t:
If s can be transformed to t, then for each i, s(i) and t(i) must have same multiset of letters.
But is this sufficient? In fact it is. Consider first the case D = 1. In this case, there’s only one subsequence for each string, s(1) and t(1), and these are just equal to s and t, respectively. The question becomes: can we make any s be any other t, assuming they have the same multiset of letters, and we can only swap consecutive letters (because D = 1)? In fact, yes! The idea is to sort s, then “unsort” it to t (i.e. take the reverse of the sequence of swaps that sort the letters of t). This works because there exists sorting algorithms that only swaps consecutive elements. (For example, insertion sort or bubble sort.)
For a general D, since we can swap consecutive letters in a subsequence s(i), one can perform a similar algorithm to transform each s(i) to t(i) (assuming they have the same multiset of letters). We have just shown that the converse to the above is true:
If for each i, s(i) and t(i) must have same multiset of letters, then s can be transformed to t.
The algorithm now is simple: just count how many times each character appears in s(i), and check that these counts are the same as those for t(i) (for each i).
A gotcha: Be careful that your implementation runs in O(N), not O(N+D)! Otherwise, your solution will exceed the time limit. (Consider a file with T = 100000, each with N = 1 and D = 100000.)
Time Complexity:
O(N)