3999. Minimum Number of String Groups Through Transformations

 1,Problem

Minimum Number of String Groups Through Transformations - LeetCode

2.Idea

Using Booth's algorithm to find minimum cyclic shift of the given string.

3.Code

 class Solution {  
   string helper(const string &s) {  
     if(s.empty()) return "";  
     int n = s.length();  
     int i = 0, j = 1, k = 0;  
     while(i < n and j < n and k < n) {  
       int val = s[(i + k) % n] - s[(j + k) % n];  
       if(val == 0) {  
         ++k; // Characters match, extend the prefix length  
       } else {  
         if(val > 0) {  
           i += k + 1; // i's substring is lexicographically larger, shift i  
         } else {  
           j += k + 1; // j's substring is lexicographically larger, shift j  
         }  
         // Ensure i and j are evaluating different starting positions  
         if(i == j) j++;  
         k = 0; // Reset matching length  
       }  
     }  
     int mini = min(i, j);  
     return s.substr(mini) + s.substr(0, mini);  
   }  
 public:  
   int minimumGroups(vector<string>& words) {  
     unordered_set<string> groups;  
     for(string &s : words) {  
       string even = "", odd = "";  
       for(int i = 0; i < s.length(); ++i) {  
         if(i & 1) odd += s[i];  
         else even += s[i];  
       }  
       groups.insert(helper(even) + "#" + helper(odd));  
     }  
     return groups.size();  
   }  
 };