HackerRank Suffix Rotation Problem Solution

HackerRank Suffix Rotation Problem Solution

Yashwant Parihar,

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;

  1. 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.
  2. 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.
  3. 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.
HackerRank Suffix Rotation Problem Solution
HackerRank Suffix Rotation Problem Solution

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()))
c C# C++ HackerRank Solutions java python