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