In this post, we will solve HackerRank Suffix Rotation Problem Solution.
Megan is playing a string game with the following rules:
- It starts with a string, 8.
- During each turn, she performs the following move:
o Choose an index in s. The chosen index must be strictly greater than any index chosen in a prior move. Perform one or more circular rotations (in either direction) of the suffix starting at the chosen index.
For example, let’s say s = abcdefjghi. During our move, we choose to do three right rotations of the suffix starting at index 6:
Note that this counts as one move.
- The goal of the game is to convert & into the lexicographically smallest possible string in as few moves as possible. In other words, we want the characters to be in alphabetical order.
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 & into the lexicographically smallest string and print that number on a new line.
Input Format
The first line contains an integer, g, denoting the number of games. Each of the g subsequent lines contains a single string denoting the initial value of string s
for a game.
Output Format
For each game, print an integer on a new line denoting the minimum number of moves required to convert into the lexicographically smallest string possible.
Sample Input 0
3 abcdefghij acab baba
Sample Output 0
0 1 2
Explanation 0
We play the following g = 3 games;
- In the first game, abcdefghij is already as lexicographically small as possible (each sequential letter is in alphabetical order). Because we don’t need to perform any moves, we print 0 on a new line.
- In the second game, we rotate the suffix starting at index 1. so acab becomes aabc.
Because the string is lexicographically smallest after one move, we print 1 on a new line. - In the third game, we perform the following moves:
- Rotate the suffix starting at index 0 (i.e… the entire string), so baba becomes abab.
- Rotate the suffix starting at index 1. so abab becomes aabb
Because the string is lexicographically smallest after two moves, we print 2 on a new
line.
Suffix Rotation C Solution
#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;
}
Suffix Rotation C++ Solution
#include <bits/stdc++.h>
using namespace std;
#define N 1010
#define inf 1010
int t;
char s[N];
map <string, int> mp;
int solve(char *s) {
// puts(s);
int len = strlen(s);
if (!len) return 0;
if (mp.count(s)) return mp[s];
char c = *min_element(s, s + len);
if (s[0] == c) return mp[s] = solve(s + 1);
int rlt = 0;
char ss[N];
int runs = 0;
bool vis[N];
for (int i = 0; i < len; i ++) if (s[i] != c) {
ss[runs] = s[i];
int prv = i ? i - 1 : len - 1;
vis[runs++] = s[prv] == c;
if (i < len - 1 && s[i+1] == c) rlt ++;
}
ss[runs] = 0;
len = runs;
c = *min_element(ss, ss + len);
bool start_c = 0;
for (int i = 0; i < len; i ++) {
if (vis[i] && ss[i] == c) {
start_c = 1; break;
}
}
int mn = inf;
char sss[N];
for (int i = 0; i < len; i ++) if (vis[i]) {
if (start_c && ss[i] != c) continue;
for (int j = 0; j < len; j ++) sss[j] = ss[(j+i)%len];
sss[len] = 0;
mn = min(mn, solve(sss));
}
return mp[s] = rlt + mn;
}
int main() {
// freopen("s.in", "r", stdin);
// freopen("s.out", "w", stdout);
scanf("%d", &t);
while (t --) {
scanf("%s", s);
printf("%d\n", solve(s));
}
return 0;
}Suffix Rotation C Sharp Solution
using System.Collections.Generic;
using System.Linq;
using System;
class Solution
{
static void Main(string[] args)
{
int q = Convert.ToInt32(Console.ReadLine());
//DateTime start = DateTime.Now;
for (int qItr = 0; qItr < q; qItr++)
{
string s = Console.ReadLine();
Console.WriteLine(new MinEdits().GetMinEdits(s));
}
//Console.Error.WriteLine(DateTime.Now - start);
}
}
public class MinEdits
{
public int GetMinEdits(string str)
{
_charsinOrder = str.OrderBy(x => x).Distinct().ToArray();
return GetMinEdits(str, 0, 0);
}
public int GetMinEdits(string str, int cost, int min)
{
if (_cache.TryGetValue(str, out var costCache))
return costCache;
var s = str.ToCharArray();
var somethingToDo = false;
char minc = _charsinOrder[min];
s = DeRepete(s, minc, out somethingToDo);
while (!somethingToDo && s.Length>1)
{
min++;
minc = _charsinOrder[min];
s = DeRepete(s, minc, out somethingToDo);
}
int costOut = 0;
if (somethingToDo)
{
costOut = Remap(s, min, cost);
}
if (costOut == 0 && cost < bestSoFar)
bestSoFar = cost;
//if(str.Length < 500)
_cache.Add(str, costOut);
return costOut;
}
private int bestSoFar = int.MaxValue;
private Dictionary<string, int> _cache = new Dictionary<string, int>();
private char[] _charsinOrder;
public char[] AsSpan(char[] s, int start, int length)
{
var result = new char[length];
for (int i = 0; i < length; i++)
{
result[i] = s[start + i];
}
return result;
}
public int Remap(char[] s, int min , int cost)
{
char mapon = _charsinOrder[min];
List<char[]> segments = new List<char[]>();
int start = 0;
char[] startSeg = null;
for (var i = 0; i < s.Length; i++)
{
if (s[i] == mapon)
{
if (start == 0)
startSeg = AsSpan(s, start, i - start).ToArray();
else
segments.Add(AsSpan(s, start, i - start));
start = i + 1;
}
}
var lengthLast = s.Length - start + startSeg.Length;
if (lengthLast > 0)
{
char[] last = new char[lengthLast];
Array.Copy(s, start, last, 0, s.Length - start);
Array.Copy(startSeg, 0, last, s.Length - start, startSeg.Length);
segments.Add(last);
}
int totalLength = segments.Sum(x => x.Length);
List<char[]> testStrings = new List<char[]>(segments.Count);
for (var j = 0; j < segments.Count; j++)
{
char[] test = new char[totalLength];
Array.Copy(segments[j], 0, test, 0, segments[j].Length);
int copied = segments[j].Length;
for (var i = 1; i < segments.Count; i++)
{
int copyindex = (j + i) % segments.Count;
Array.Copy(segments[copyindex], 0, test, copied, segments[copyindex].Length);
//test += segments[];
copied += segments[copyindex].Length;
}
testStrings.Add(test);
}
if ((min + 1 >= _charsinOrder.Length))
{
}
bool opt = testStrings.Any(x => x[0] == _charsinOrder[min + 1]);
int lowestScore = int.MaxValue;
foreach (var test in testStrings)
{
if (!opt || test[0] == _charsinOrder[min + 1])
{
var testScore = GetMinEdits(new string(test), cost + segments.Count, min + 1);
if (lowestScore > testScore)
lowestScore = testScore;
}
}
return lowestScore + segments.Count;
}
private char[] DeRepete(char[] s, char min, out bool somethingToDo)
{
somethingToDo = false;
List<char> res = new List<char>(s.Length);
if (s[0] != min)
res.Add(s[0]);
for (int i = 1; i < s.Length; i++)
{
if (s[i] != s[i - 1])
{
res.Add(s[i]);
somethingToDo = somethingToDo || s[i] == min;
}
}
if (res.Count <= 1)
somethingToDo = false;
return res.ToArray();
}
}Suffix Rotation Java Solution
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();
}
}Suffix Rotation Python Solution
#!/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()))
