Suffix Rotation – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Suffix Rotation HackerRank 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;
}
Java Suffix Rotation HackerRank Solution
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.stream.*;
public class Solution {
static String s;
static int n;
static char maxInS, minInS;
static Char[] CharArr;
static Char[][] CharPos;
static TreeMap<Char,Integer> minRots;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int g = in.nextInt();
for (int go=0; go<g; go++) {
s = in.next();
n = s.length();
minInS = (char)(s.chars().min().getAsInt());
maxInS = (char)(s.chars().max().getAsInt());
CharArr = new Char[n];
CharPos = new Char[n][n];
minRots = new TreeMap<Char,Integer>((c1,c2) -> (c1.c != c2.c ?
Character.compare(c1.c,c2.c) : Integer.compare(c1.i,c2.i)));
for (int i=0; i<n; i++) CharArr[i] = new Char(s.charAt(i), i);
for (int i=0; i<n; i++) for (int j=0; j<n; j++)
CharPos[i][j] = CharArr[(i+j)%n];
System.out.println(minRot(0,minInS));
}
}
private static int minRot(int pos, char minC) {
Char point = new Char(minC, pos);
Integer ans = minRots.get(point);
char nextC = (char)(minC+1);
if (ans == null) {
if (minC == maxInS) ans = 0;
else if (s.indexOf(minC) < 0) ans = minRot(pos, nextC);
else {
Char[] rotstr = Arrays.stream(CharPos[pos]).filter(c -> (c.c >= minC))
.toArray(Char[]::new);
// System.out.println(rotstr[0].c +"\t"+ rotstr[0].i +"\t"+ minC +"\t"+ pos);
//Arrays.stream(rotstr).mapToInt(c->c.i).forEach(i->System.out.print(" "+i));
//System.out.println(" "+minC);
int m = rotstr.length;
ArrayList<Integer> posses = new ArrayList<Integer>();
int globs = 0;
int i = 0;
boolean startC = false; int startI = 0;
if (rotstr[0].c == minC) {
startC = true;
for (; rotstr[i].c == minC; i++);
posses.add(rotstr[i%m].i);
startI = rotstr[i%m].i;
}
for (; i<m; i++) {
if (rotstr[i].c == minC) {
globs++;
for (; i < m && rotstr[i].c == minC; i++);
if (i != m) posses.add(rotstr[i%m].i);
else if (!startC) posses.add(rotstr[i%m].i);
// System.out.println("\t"+ rotstr[i%m].i);
}
}
// System.out.println(globs);
final boolean begmin = startC, endmin = rotstr[m-1].c == minC;
final int begI = startI, gl = globs;
ans = globs +
posses.stream()
.mapToInt(p -> minRot(p,nextC) + ((p==begI && begmin && gl > 0) ?
1 - (endmin? 1 : 0) : 0))
.min().getAsInt();
}
minRots.put(point, ans);
}
return ans;
}
private static class Char {
char c; int i;
public Char(char _c, int _pos) {c = _c; i = _pos;}
}
}
Python 3 Suffix Rotation HackerRank Solution
def tek(lista,tal = None):
if tal != None:
lista2 = lista[tal:] + lista[:tal]
print("".join([chr(ord('a')+i) for i in lista]),"".join([chr(ord('a')+i) for i in lista2]))
print(" "*(tal) + "^")
else:
print(*[chr(ord('a')+i) for i in lista],sep="")
def brute(S):
if len(S)==0:
return 0
c_min = -1
while min(S)!=c_min:
c_min = min(S)
while S[0]==c_min:
S = S[1:]
if len(S)==0:
return 0
mini = 78678687687
for ind,num in enumerate(S):
if num == c_min:
mini = min(mini,brute(S[ind+1:]+S[:ind]))
return mini + 1
def secondVal(S):
x = S[0]
ind = 0
while S[ind]==x:
ind+=1
if ind>= len(S):
return ind
return ind
cost = {}
def concept(S):
if len(S)==0:
return 0
prev = 0
Snew = []
for c in S:
if c!=prev:
prev = c
Snew.append(c)
S = tuple(Snew)
if S not in cost:
cs = min(S)
while S[0]==cs:
cut_index = secondVal(S)
S = S[cut_index:]
if len(S)==0:
return 0
cs = min(S)
ind_c = []
cutted_S = []
cutted_id = 0
for ind,test_c in enumerate(S):
if test_c == cs:
ind_c.append(cutted_id)
else:
cutted_S.append(test_c)
cutted_id += 1
cutted_S = tuple(cutted_S)
mini = 2984924
for ind in ind_c:
mini = min(mini,concept(cutted_S[ind:]+cutted_S[:ind])+len(ind_c))
cost[S] = mini
return cost[S]
def closeconcept(S,cs):
possi = [False]*len(S)
cost = [10000]*len(S)
possi[0]=True
for c in sorted(list(set(S))):
ind_c = []
for ind,test_c in enumerate(S):
if test_c == c:
ind_c.append(ind)
new_possi = [False]*len(S)
newcost = [100000]*len(S)
for i in range(len(S)):
if possi[i]:
for ind in ind_c:
newind = (i+ind) % len(S)
newpossi[newind] = True
if ind == 0:
newcost[newind] = min(newcost[newind], cost[i])
else:
newcost[newind] = min(newcost[newind], cost[i]+1)
def onefirst(d, ind1,ind2):
start1 = ind1
start2 = ind2
n = len(d)
while d[ind1]==d[ind2]:
prevd1 = d[ind1]
prevd2 = d[ind2]
ind1 = (ind1 + 1) % n
ind2 = (ind2 + 1) % n
if ind1 == start1:
return True
if prevd1 > d[ind1]:
return True
if prevd2 > d[ind2]:
return False
if d[ind1] < d[ind2]:
return False
else:
return True
q = int(input())
for _ in range(q):
data = [ord(x)-ord('a') for x in input()]
prev = -1#min(data)
d = []
for c in data:
if c!=prev:
prev = c
d.append(c)
d = tuple(d)
if len(d)==0 or d==sorted(d):
print(0)
continue
#print(concept(d))
#print(brute(d))
Sc = sorted(tuple(set(d)))
S = [()]*len(Sc)
markers = [[] for x in range(len(Sc)-1)]
mapps = [()]*(len(Sc)-1)
firsttimers = [set() for x in range(len(Sc)-1)]
S[0] = d
for ind,c in enumerate(Sc[:-1]):
# Remove character c
cutS = []#[a for a in S[ind] if a!=c]
cutIndex = 0
cutIndecies = []
mapp = []
for a_ind,a in enumerate(S[ind]):
if a!=c:
cutS.append(a)
mapp.append(cutIndex)
cutIndex+=1
else:
mapp.append(cutIndex)
cutIndecies.append(a_ind)
firsttime = set()
if len(cutIndecies)>0:
circular = [cutIndecies[-1]] + cutIndecies
for cutsind,cuts in enumerate(cutIndecies):
if (cuts-circular[cutsind])%len(S[ind]) != 1:
firsttime.add(cuts)
#mapp = [x%len(cutS) for x in mapp]
# # Remove dubl
#
# temp = [cutS[0]]
# mark = [cutmarker[0]]
#
# for ind,c in enumerate(cutS[1:-1]):
# fore = cutS[ind-1]
# nesta = cuts[ind+1]
#
# if c!=fore or c!=nesta:
# temp.append(c)
# mark.append(cutmarker[ind])
# prevprev = prev
# prev = c
#
# temp = [cutS[-1]]
# mark = [cutmarker[-1]]
S[ind+1] = tuple(cutS)
mapps[ind] = tuple(mapp)
markers[ind] = tuple(cutIndecies)
firsttimers[ind] = firsttime
d_superconcept = [{} for _ in range(len(Sc))]
def superconcept(rot,k,n):
if k == 0:
return 0
if rot not in d_superconcept[k]:
newrots = [mapps[n-k-1][cut] for cut in markers[n-k-1]]
oldrot = mapps[n-k-1][rot]
#tek(S[n-k-1],rot)
#print("Vill rotera till", markers[n-k-1])
#tek(S[n-k])
#print("Möjliga slutpos", newrots)
mini = 743874387
# for ind,newrot in enumerate(newrots):
# if len(firsttimers[n-k-1])==1 and rot == markers[n-k-1][ind] and rot in firsttimers[n-k-1]:
# cost = len(firsttimers[n-k-1])-1
# elif rot != markers[n-k-1][ind] and rot in firsttimers[n-k-1]:
# cost = len(firsttimers[n-k-1])-1
# else:
# cost = len(firsttimers[n-k-1])
# print("cost",cost,"genom att",markers[n-k-1][ind],"len firsttimers",len(firsttimers[n-k-1]),firsttimers[n-k-1])
for ind,newrot in enumerate(newrots):
if len(firsttimers[n-k-1])==1 and rot == markers[n-k-1][ind] and rot in firsttimers[n-k-1]:
cost = len(firsttimers[n-k-1])-1
elif rot != markers[n-k-1][ind] and rot in firsttimers[n-k-1] and markers[n-k-1][ind] in firsttimers[n-k-1]:
cost = len(firsttimers[n-k-1])-1
else:
cost = len(firsttimers[n-k-1])
#print("cost",cost,"genom att",markers[n-k-1][ind],"len firsttimers",len(firsttimers[n-k-1]),firsttimers[n-k-1])
mini = min(mini,superconcept(newrot%len(S[n-k]),k-1,n)+cost)
#print("cost",cost,"extracost",superconcept(newrot,k-1,n)+cost,k)
d_superconcept[k][rot] = mini
return d_superconcept[k][rot]
superOUT = superconcept(0,len(Sc)-1,len(Sc))
#bruteOUT = brute(d)
#if superOUT != bruteOUT:
# print(superOUT,bruteOUT)
# tek(d)
print(superOUT)
#print(d_superconcept)
#print(brute(d))
# print(markers)
# ababsbfbs
# bbsbfbs
# aaaa bcdeb
# aaaa debbc
#udfudfg
#(fgufu)
#gufu
#(fugu)
#ugu
#uu
# udfudfg
#(dfudfgu)
# ufgu
#(fguu)
#guu
# udfudfg
# dfudfgu
# ddfgufu
# ddffugu
# ddffguu
# udfudfg
# dfgudfu
# ddfufgu
# ddffguu
Python 2 Suffix Rotation HackerRank Solution
#!/bin/python
import sys
def convert(s):
lens = len(s)
temp = [0] * 26
for i in xrange(lens):
c = ord(s[i]) - ord('a')
temp[c] = 1
m = 0
for c in xrange(26):
if temp[c]:
temp[c] = m
m += 1
a = []
loc = [[] for i in xrange(m)]
prev = -1
p = 0
for i in xrange(lens):
c = ord(s[i]) - ord('a')
c = temp[c]
if c != prev:
a.append(c)
prev = c
loc[c].append(p)
p += 1
return a, loc, m
#assert(convert('hzzzzhhhhiiii') == ([0, 2, 0, 1], [[0, 2], [3], [1]], 3))
a = q = loc = []
n = m = 0
def solve(x, pos):
if x == m-1:
return 0
if q[x][pos] != -1:
return q[x][pos]
result = n
if a[pos] < x:
result = solve(x, (pos+1) %n)
else:
not_vip = []
for p in loc[x]:
i = p
while a[i] <= x:
i = (i+1) % n
if a[i] == x:
not_vip.append(i)
vip = list(set(loc[x]) - set(not_vip))
vip_count = len(vip)
for p in vip:
value = solve(x+1, p) + (vip_count-1 if pos in vip and (p != pos or vip_count == 1) else vip_count)
result = min(result, value)
q[x][pos] = result
#print 'q[%d][%d] = %d' % (x, pos, result)
return result
queries = int(raw_input().strip())
for a0 in xrange(queries):
s = raw_input().strip()
a, loc, m = convert(s)
n = len(a)
q = [[-1] * n for i in xrange(m)]
print solve(0, 0)
C Suffix Rotation HackerRank 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;
// FOR(i,0,n) printf ("%d -> %d\n",i,nx[i]);
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]]);
// printf ("%d -> %d\n",i,b2);
if (b2<b1)
{
int temp = b1;
b1 = b2;
b2 = temp;
pb1=i;
}
}
// printf ("%d %d %d ???\n",sum,b1,pb1);
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;
}
}
// FOR(i,0,n) printf ("%d %d %d\n",i,isti[i],nju[i]);
// printf ("\n");
}
printf ("%d\n",nju[0]);
}
int main(){
int znj;
scanf ("%d",&znj);
while(znj--) solve();
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
