In this HackerRank Suffix Rotation problem solution, Megan plays this game G times, starting with a new string S each time. For each game, find the minimum number of moves necessary to convert S into the lexicographically smallest string and print that number on a new line.

HackerRank Suffix Rotation problem solution


Problem solution in Python.

#!/bin/python3

import sys

def bestlastrotation(s,groups,letters,memos):
    if len(letters) < 3:
        return groups[0]
    mn = letters[0]
    mn2 = letters[1]
    mn3 = letters[2]
    lens = len(s)
    
    groups2 = []
    for g in groups:
        i = g
        while s[i] == mn:
            i = (i + 1) % lens
        if s[i] == mn2 and s[g-1] != mn2:
            groups2.append([g,i])
    
    if len(groups2) == 0: return groups[0]
    if len(groups2) == 1: return groups2[0][0]
    
    
    for gg in groups2:
        j = gg[1]
        while s[j] == mn2 or s[j] == mn:
            j = (j + 1) % lens
        if s[j] != mn3:
            return gg[0]
        else:
            gg.append(j)
    
    if len(letters) < 4:
        return groups2[0][0]
    
    
    groupset = set(x[0] for x in groups2)
    
    ans = 0
    best = lens
    for g in groupset:
        s2 = (s[g:]+s[:g]).replace(mn,'')
        result = min_rotations(s2,memos)
        if best > result:
            best = result
            ans = g  
    
    
    return ans



def min_rotations(s,memos):
    if s in memos:
        return memos[s]
    
    letters = sorted(set(s))
    mn = min(letters)
    ans = 0
        
    while mn != max(letters):
        
        i = 0
        while s[i] == mn:
            i += 1
        if i > 0:
            s = s[i:]
        
        groups = []
        for i in range(len(s)):
            if s[i] == mn and s[i-1] != mn:
                groups.append(i)
        
        ans += len(groups)
        
        if len(groups) == 1:
            g = groups[0]
            s = s[g:] + s[:g]
        
        if len(groups) > 1:
            g = bestlastrotation(s,groups,letters,memos)
            s = s[g:] + s[:g]
        
        s = s.replace(mn,'')
        letters = letters[1:]
        mn = min(letters)
    
    memos[s] = ans
    return ans
    

q = int(input().strip())
for a0 in range(q):
    s = input().strip()
    # your code goes here
    print(min_rotations(s,dict()))

{"mode":"full","isActive":false}


Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static int copy(List<Character> sorg, char[] dest, int startSorg, int endSorg, int startDest) {
    for (int j = startSorg; j < endSorg; j++) {
      dest[startDest++] = sorg.get(j);
    }
    return startDest;
  }

  static int copy(char[] sorg, char[] dest, int startSorg, int endSorg, int startDest) {
    for (int j = startSorg; j < endSorg; j++) {
      dest[startDest++] = sorg[j];
    }
    return startDest;
  }

  static char[] create(List<Character> sorg, int startSorg, int endSorg) {
    char[] dest = new char[endSorg - startSorg];
    copy(sorg, dest, startSorg, endSorg, 0);
    return dest;
  }

  static int solve(char[] s) {
    int res = 0;
    char prev1 = 0;
    List<Character> t = new ArrayList<>();
    char a = s[0];
    for (char c : s) {
      if (c != prev1) {
        t.add(c);
      }
      prev1 = c;
      if (a > c) {
        a = c;
      }
    }
    if (t.size() > 0 && t.get(0) == a) {
      if (t.size() == 1) {
        return 0;
      }
      return solve(create(t, 1, t.size()));
    }
    List<char[]> parts = new ArrayList<>();
    int prev = -1;
    res = 0;
    for (int i = 0; i < t.size(); i++) {
      if (t.get(i) != a) {
        continue;
      }
      parts.add(create(t, prev + 1, i));
      res++;
      prev = i;
    }
    char[] v = new char[t.size() - (prev + 1) + parts.get(0).length];
    int start = copy(t, v, prev + 1, t.size(), 0);
    copy(parts.get(0), v, 0, parts.get(0).length, start);
    parts.set(0, v);
    int bi = -1;
    int bq = 0;
    for (int i = 0; i < parts.size(); i++) {
      char b = parts.get(i)[0];
      int h = i > 0 ? i - 1 : parts.size() - 1;
      char z = parts.get(h)[parts.get(h).length - 1];
      char c = 0;
      int ii = i;
      int jj = 0;
      while (true) {
        jj++;
        if (jj == parts.get(ii).length) {
          ii = (ii + 1) % parts.size();
          jj = 0;
        }
        if (ii == i && jj == 0) {
          break;
        }
        if (parts.get(ii)[jj] != b) {
          c = parts.get(ii)[jj];
          break;
        }
      }
      if (c == 0) {
        c = b;
      }
      int q = (((int) b) * 1024) + ((z != b ? 0 : 1) * 256) - ((int) c);
      if (bi == -1 || q < bq) {
        bq = q;
        bi = i;
      }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = bi; i < parts.size(); i++) {
      sb.append(parts.get(i));
    }
    for (int i = 0; i < bi; i++) {
      sb.append(parts.get(i));
    }
    if (sb.length() == 0) {
      return res;
    }
    return res + solve(sb.toString().toCharArray());
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int q = Integer.parseInt(st.nextToken());

    for (int qItr = 0; qItr < q; qItr++) {
      String s = br.readLine();

      System.out.println(solve(s.toCharArray()));
    }

    br.close();
  }
}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;



using namespace std;
map<string,int> results[1001];
int solve(string S){
    int s=S.size();
    if(s==1||s==0) return 0;
    if(results[s].find(S)!=results[s].end()) return results[s][S];
    if(S[0]=='a'){
        
        int i=1;
        while(i<s&&S[i]=='a') i++;
        if(i==s){
            results[s][S]=0;
            return 0;
        }
        string T=S.substr(i);
        
        if(T.find('a')== std::string::npos){
            int t=T.size();
            for(int j=0;j<t;j++) T[j]--;
        }
        
        results[s][S]=solve(T);
        return results[s][S];
    }
    vector<pair<int,int>> p;
    vector<pair<int,int>> bf;
    std::string::size_type last=S.find('a');
    int ans=s;
    while(last!=std::string::npos){
        p.push_back(make_pair(last,0));
        while(last+1<s&&S[last+1]=='a') last++;
        p.back().second=last;
        if(last+1==s){
            if(S[0]=='b') bf.push_back(p.back());
        }
        else{
            if(S[last+1]=='b')bf.push_back(p.back());
        }
        last=S.find('a',last+1);
    }
    if(p.size()==1){
        string T="";
        int a=p.front().second;
        if(a<s-1) T+=S.substr(a+1);
        T+=S.substr(0,p.front().first);
        int t=T.size();
        for(int i=0;i<t;i++) T[i]--;
        ans=1+solve(T);
    }
    else{
        if(bf.size()==0){
            string T="";
            int next=0;
            for(auto a:p){
                T+=S.substr(next,(a.first-next));
                next=a.second+1;
            }
            if(next!=s)T+=S.substr(next);
            int t=T.size();
            int q=p.front().first;
            
            for(int i=0;i<t;i++) T[i]--;
            
            string Q=T.substr(q);
            Q+=T.substr(0,q);
            ans=p.size()+solve(Q);
        }
        else{
            string T="";
            int next=0;
            int pans=p.size();
            for(auto a:p){
                T+=S.substr(next,(a.first-next));
                next=a.second+1;
            }
            if(next!=s)T+=S.substr(next);
            next=0;
            int t=T.size();
            for(int i=0;i<t;i++) T[i]--;
            vector<pair<int,int>>::iterator itp=p.begin();
            int z=0;
            for(vector<pair<int,int>>::iterator itbf=bf.begin();itbf!=bf.end();itbf++){
                while(itp!=p.end()&&((*itp).first<=(*itbf).first)){
                    z+=(*itp).first-next;
                    next=(*itp).second+1;
                    itp++;
                }
                string Q="";
                if(z!=t){
                    Q+=T.substr(z);
                }
                Q+=T.substr(0,z);
                ans=min(ans,pans+solve(Q));
            }
        }
    }
    results[s][S]=ans;
    return ans;
}
int main(){
    int q;
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        string s;
        cin >> s;
        map<char,int> count;
        for(auto a:s) count[a]++;
        char next='a';
        map<char,char> chan;
        for(auto a:count){
            chan[a.first]=next;
            next++;
        }
        int n=s.size();
        for(int i=0;i<n;i++){
            s[i]=chan[s[i]];
        }

        cout<<solve(s)<<endl;
    }
    return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define FOR(a,b,c) for(int a=(b),_for=(c);a<_for;++a)
#define M 1000
#define Z 26
char c[M+5];
int n, P[M+5], A[M+5], B[M+5], C[Z+5], D[M+5], E[M+5];
int min(int a, int b)
{
    return a < b ? a : b;
}

int n;
int p[M+5];
char c[M+5];
int cnt[Z+5];
int dp[M+5];
int nju[M+5];
int nx[M+5];
int isti[M+5];

void solve(){
    scanf ("%s",c);
    n=strlen(c);
    FOR(i,0,n) p[i]=Z-1-(c[i]-'a');
    FOR(i,0,Z) cnt[i]=0;
    FOR(i,0,n) cnt[p[i]]++;
    FOR(i,0,n) dp[i]=0;
    FOR(i,0,n) nju[i]=0;
    FOR(i,0,n) nx[i]=0;
    FOR(i,0,n) isti[i]=0;
    FOR(cl,0,Z){
        if (!cnt[cl]) continue;
        FOR(i,0,n) dp[i]=nju[i];
        memset(nju,-1,n*sizeof(int));
        memset(isti,0,n*sizeof(int));
        int last=-1,prvi=-1,sum=0,b1=n,b2=n;
        FOR(i,0,n) if (p[i]<=cl){
            if (last>=0){
                nx[last]=i;
                if (p[last]!=p[i] && p[i]==cl) isti[i]=1,sum++;
            }
            else prvi=i;
            last=i;
        }
        nx[last]=prvi;

        if (p[last]!=p[prvi] && p[prvi]==cl) isti[prvi]=1,sum++;
        int pb1=-1;
        FOR(i,0,n) if (p[i]==cl && p[nx[i]]!=cl){
            b2=min(b2,dp[nx[i]]);

            if (b2<b1)
            {
                int temp = b1;
                b1 = b2;
                b2 = temp;
                pb1=i;
            }
        }

        sum+=b1-1;
        if (pb1==-1) sum=-1;
        bool flag=0;
        FOR(i,0,n){
            if (p[i]>cl) continue;
            if (p[i]<cl || !isti[i]){
                nju[i]=sum+1;
                continue;
            }
            if (b1==b2 || b2==n){
                nju[i]=sum;
                continue;
            }
            nju[i]=sum;
            flag=1;
        }
        if (flag){
            for (int i=pb1;i>=0 && flag;--i){
                if (isti[i]) nju[i]++,flag=0;
            }
            for (int i=n-1;i>=0 && flag;--i){
                if (isti[i]) nju[i]++,flag=0;
            }
        }

    }
    printf ("%d\n",nju[0]);
    
}

int main(){
    int znj;
    scanf ("%d",&znj);
    while(znj--) solve();
    return 0;
}

{"mode":"full","isActive":false}