HackerRank Suffix Rotation problem solution YASH PAL, 31 July 2024 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())) {“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 ("%dn",nju[0]); } int main(){ int znj; scanf ("%d",&znj); while(znj--) solve(); return 0; } {“mode”:”full”,”isActive”:false} Algorithms coding problems solutions