Hard
You are given an array of strings words.
Define a transformation on a string s as follows:
E be the subsequence of characters at even indices of s.O be the subsequence of characters at odd indices of s.E and O by any number of positions to the right, possibly zero.E characters back into even indices and the shifted O characters back into odd indices.Two strings are equivalent if one can be transformed into the other by a single transformation.
Partition words into the minimum number of groups such that:
Return an integer denoting the minimum number of groups.
Example 1:
Input: words = [“ntgwz”,”zwntg”]
Output: 1
Explanation:
"ntgwz", the even-index subsequence is "ngz" and the odd-index subsequence is "tw"."ngz" right by 1 position to obtain "zng", and shift "tw" right by 1 position to obtain "wt"."zwntg".Example 2:
Input: words = [“abc”,”cab”,”bac”,”acb”,”bca”,”cba”]
Output: 3
Explanation:
The strings can be partitioned into the following groups:
["abc","cba"]["cab","bac"]["acb","bca"]Example 3:
Input: words = [“leet”,”abb”,”bab”,”deed”,”edde”,”code”,”bba”]
Output: 5
Explanation:
The strings can be partitioned into the following groups:
["abb","bba"]["deed","edde"]["leet"]["bab"]["code"]All pairs of strings in each group are equivalent.
Constraints:
1 <= words.length <= 1051 <= words[i].length <= 5 * 105words[i].length does not exceed 5 * 105.words[i] consist of lowercase English letters.import java.util.HashSet;
public class Solution {
public int minimumGroups(String[] words) {
HashSet<Long> set = new HashSet<>();
for (String w : words) {
int n = w.length();
int evenLen = (n + 1) >> 1;
int oddLen = n >> 1;
char[] even = new char[evenLen];
char[] odd = new char[oddLen];
int ei = 0;
int oi = 0;
for (int i = 0; i < n; i++) {
if ((i & 1) == 0) {
even[ei++] = w.charAt(i);
} else {
odd[oi++] = w.charAt(i);
}
}
int eStart = booth(even);
int oStart = booth(odd);
long h1 = hash(even, eStart);
long h2 = hash(odd, oStart);
long key = h1 * 1000003L + h2;
set.add(key);
}
return set.size();
}
private int booth(char[] s) {
int n = s.length;
if (n <= 1) {
return 0;
}
int i = 0;
int j = 1;
int k = 0;
while (i < n && j < n && k < n) {
char a = s[(i + k) % n];
char b = s[(j + k) % n];
if (a == b) {
k++;
} else if (a > b) {
i += k + 1;
if (i <= j) {
i = j + 1;
}
k = 0;
} else {
j += k + 1;
if (j <= i) {
j = i + 1;
}
k = 0;
}
}
return Math.min(i, j);
}
private long hash(char[] s, int start) {
long h = 0;
for (int i = 0; i < s.length; i++) {
h = h * 131 + s[(start + i) % s.length];
}
return h;
}
}