Intro...

My competitive programming memo's and libraries...

Code formatter:
http://codeformatter.blogspot.com/

Awesome poj problem lists:
Data Structure Practice: for Collegiate Programming Contests and Education
Algorithm Design Practice for Collegiate Programming Contests and Education
https://github.com/gongzhitaao/oj/tree/master/poj
Algorithm Contest Problem Summary
http://tozangezan.hatenablog.com/entry/20111111/1320993464
セグメント木 問題集
CS 97SI
Geometry problems from POJ 
https://odan-null.hatenadiary.org/entry/20130114/1358162397

Checklist:

Start background noise

Pop Hits | Free Internet Radio | TuneIn

Set before 5min alarm

Online Timer (timeanddate.com)

brute force?

exp? sample work?

greedy?

binary search?

dp?

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();  
   }  
 };