HackerRank Yet Another KMP Problem Solution
In this post, we will solve HackerRank Yet Another KMP Problem Solution.
This challenge uses the famous KMP algorithm. It isn’t really important to understand how KMP works, but you should understand what it calculates.
A KMP algorithm takes a string, S, of length N as input. Let’s assume that the characters in S are indexed from 1 to N; for every prefix of S, the algorithm calculates the length of its longest valid border in linear complexity. In other words, for every & (where 1 < i < N) it calculates the largest (where 0 <l<i-1) such that for every p (where 1≤ p < 1) there is S[p] = S[i-1+p].
Here is an implementation example of KMP:
kmp[1] = 0;
for (i = 2; i <= N; i = i + 1){
l = kmp[i - 1];
while (l > 0 && S[i] != S[l + 1]){
l = kmp[l];
}
if (S[i] == S[l + 1]){
kmp[i] = l + 1;
}
else{
kmp[i] = 0;
}
}
Sample Input
2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output
aabb
Yet Another KMP Problem C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int letter = 0, min=26, first = -1;
int data[27];
data[26]=1000001;
for(int i = 0; i < 26; i++){
scanf("%d",data+i);
if(data[i]) {
if (first<0) first = i;
letter++;
if(data[i]<data[min]) min = i;
}
}
if(letter == 1) {
for(int i = 0; i < data[min]; i++) {
putchar('a'+min);
}
return 0;
}
if (min==first) {
putchar('a'+min);
int index_m = 1;
for (int l = first + 1; l < 26; l++) {
for (int i = 0; i<data[l]; i++) {
if(index_m++ < data[min]) putchar('a'+min);
putchar('a'+l);
}
}
} else {
putchar('a'+min);
data[min]--;
for (int l = first; l < 26; l++) {
for (int i = 0; i<data[l]; i++) {
putchar('a'+l);
}
}
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
Yet Another KMP Problem C++ Solution
#include <bits/stdc++.h>
using namespace std;
#define INTMAX 0x7FFFFFFF
#define INTMIN -0x80000000
#define LONGMAX 0x7FFFFFFFFFFFFFFF
#define LONGMIN -0x8000000000000000
int main(){
ios_base::sync_with_stdio(false);
int n = 0;
int notzero = 0;
int fi = -1;
int x[26];
for(int i=0; i<26; i++){
cin>>x[i];
if( x[i]>0 && (fi==-1||x[i]<x[fi]) )
fi = i;
n += x[i];
if(x[i]!=0)
notzero++;
}
//cout<<n<<" "<<notzero<<" "<<fi<<endl;
if(notzero==1){
string s;
for(int i=0; i<26; i++){
for(int j=0; j<x[i]; j++)
s += ('a'+i);
}
cout<<s;
}
else{
string s;
vector<char> fir, rest;
for(int i=0; i<26; i++){
for(int j=0; j<x[i]; j++){
if(i==fi)
fir.push_back('a'+i);
else
rest.push_back('a'+i);
}
}
if(rest[0]<fir[0]){
s += fir[0];
x[fir[0]-'a']--;
for(int i=0; i<26; i++){
for(int j=0; j<x[i]; j++){
s += ('a'+i);
}
}
}
else if(x[fi]==1){
s += fir[0];
x[fir[0]-'a']--;
for(int i=0; i<26; i++){
for(int j=0; j<x[i]; j++){
s += ('a'+i);
}
}
}
else{
int ind = 0;
s += fir[0];
x[fir[0]-'a']--;
s += fir[0];
x[fir[0]-'a']--;
for(int i=0; i<x[fi]; i++){
s += rest[ind];
ind++;
s += fir[0];
}
while(ind<rest.size()){
s += rest[ind];
ind++;
}
}
cout<<s;
}
}Yet Another KMP Problem C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution {
/*
* Complete the kmp function below.
*/
static string kmp(int[] x) {
StringBuilder sbRes = new StringBuilder();
Dictionary<char,int> dic = mapping(x);
int ind = getMin(dic);
sbRes.Append(getLetter(ind),1);
dic[getLetter(ind)]--;
char c = dic.First().Key;
// check if the minimum index is of the first letter
if (getLetter(ind) == c && dic.Keys.Count >1){
c = dic.Skip(1).First().Key;
// cross appending the first and second letters
for (int i=0; i< dic[getLetter(ind)]; i++){
sbRes.Append(getLetter(ind));
sbRes.Append(c);
}
// substracting the number of letters already appended
dic[c] -= dic[getLetter(ind)];
dic[getLetter(ind)] =0;
}
foreach(char key in dic.Keys)
{
sbRes.Append(key, dic[key]);
}
return sbRes.ToString();
/* Console.Write(ind);
char c = dic.First().Key;
if (getLetter(ind) == c){
c = dic.Skip(1).First().Key;
}
for (int i=0; i< dic[getLetter(ind)]; i++){
sbRes.Append(getLetter(ind));
sbRes.Append(c);
}
dic[c] -= dic[getLetter(ind)];
dic[getLetter(ind)] =0;*/
}
static Dictionary<char,int> mapping(int[] x)
{
Dictionary<char,int> dic = new Dictionary<char,int>();
for (int i=0; i< x.Length; i++){
if(x[i] > 0)
dic.Add(getLetter(i), x[i]);
}
return dic;
}
static int getMin(Dictionary<char,int> dic){
char item = dic.Aggregate((l, r) => l.Value <= r.Value ? l : r).Key;
int ind =getNumber(item);
return ind;
}
static char getLetter(int i)
{
int a= (int)'a';
char c = Convert.ToChar(a+i);
return c;
}
static int getNumber(char c)
{
int a= (int)'a';
int i = (int)c - a;
return i;
}
static int[] KMP(string str)
{
long len = str.Length;
int[] kmp = new int[len];
int l =0;
kmp[0]=l;
for (int i = 1; i < len; i++){
l = kmp[i - 1];
while (l > 0 && str[i] != str[l]){
l = kmp[l-1];
}
if (str[i] == str[l]){
kmp[i] = l + 1;
}
else{
kmp[i] = 0;
}
}
return kmp;
}
static string getMinString(List<string> lst, string str)
{
long n_min = str.Length;
string s_min = str;
int[] res;
long val;
foreach(string perm in lst)
{
res = KMP(perm);
val = sumAll(res);
if( val < n_min){
n_min = val;
s_min= perm;
}
}
return s_min;
}
static long sumAll(int[] num){
long sum =0;
for (int i=0; i< num.Length; i++)
{
sum+=num[i];
}
return sum;
}
static void Main(string[] args) {
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int[] x = Array.ConvertAll(Console.ReadLine().Split(' '), xTemp => Convert.ToInt32(xTemp))
;
string result = kmp(x);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}Yet Another KMP Problem Java Solution
import java.io.*;
import java.util.*;
public class KMP {
public static void main(String[] args) {
char ch='a',ch1;
String s1="";
int ar[]=new int [26];
int min=99999999,loc=0;
int loc2=0;
Scanner in=new Scanner(System.in);
int k=0;
for(int i=0;i<26;i++){
ar[i]=in.nextInt();
if(ar[i]<min && ar[i]!=0){
min=ar[i];loc=i;
}
if(ar[i]!=0){
k++;
if(k==2) {
loc2 = i;
}
}
}
ch1=(char)(97+loc);
ar[loc]=ar[loc]-1;
s1=s1+Character.toString(ch1);
if(ar[loc]<ar[loc2]) {
ch1 = (char) (97 + loc);
char ch2 = (char) (97 + loc2);
int len1 = ar[loc];
if(ch1<ch2) {
s1 = s1 + new String(new char[len1]).replace("\0", Character.toString(ch1) + Character.toString(ch2));
ar[loc2] = ar[loc2] - len1;
ar[loc] = ar[loc] - len1;
}
}
for(int i=0;i<26;i++){
String s=new String(new char[ar[i]]).replace("\0",Character.toString(ch));
s1=s1+s;
++ch;
}
System.out.println(s1);
}
}Yet Another KMP Problem JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
function getMinIndex(x) {
var min = Number.MAX_VALUE;
var idx = -1;
for(var i=0;i<x.length;i++) {
if (x[i]>0 && x[i]<min) {
min = x[i];
idx = i;
}
}
return idx;
}
function calculateLeftRight(x, idx) {
var left = -1;
var right = -1;
for(var i=0;i<x.length;i++) {
if (x[i]>0) {
if (left<0 && i<idx)
left = i;
if (right<0 && i>idx)
right = i;
}
if (left >=0 && right >=0) break;
}
return [left, right];
}
function take(x, i) {
x[i]--;
return String.fromCharCode('a'.charCodeAt(0) + i);
}
function minLex(x) {
var s = "";
for(var i=0;i<x.length;i++) {
for(var j=0;j<x[i];j++) {
s+= String.fromCharCode('a'.charCodeAt(0) + i);
}
}
return s;
}
/*
* Complete the kmp function below.
*/
function kmp(x) {
/*
* Write your code here.
*/
var minIdx= getMinIndex(x);
var lr = calculateLeftRight(x, minIdx);
var output = "";
output += take(x, minIdx);
if (x[minIdx]<2 || lr[0]>=0 || (lr[0]<0 && lr[1]<0)) {
output += minLex(x);
} else {
var cnt = x[minIdx];
for(var i=0;i<cnt;i++) {
output += take(x, minIdx);
output += take(x, lr[1]);
}
output += minLex(x)
}
return output;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const x = readLine().split(' ').map(xTemp => parseInt(xTemp, 10));
let result = kmp(x);
ws.write(result + "\n");
ws.end();
}Yet Another KMP Problem Python Solution
import string
xs = list(map(int,input().split()))
ys = map(list,filter(lambda p: p[0] != 0, zip(xs, string.ascii_lowercase)))
ys = list(sorted(ys))
c = ys[0][1]
ys[0][0] -= 1
if ys[0][0] == 0:
del ys[0]
ys = list(sorted(ys, key=lambda p: p[1]))
s = [c]
while ys:
i = 0
if len(s) >= 2 and len(ys) >= 2 and s[0] == s[1] == s[-1] == c == ys[i][1]:
i = 1
s.append(ys[i][1])
ys[i][0] -= 1
if ys[i][0] == 0:
del ys[i]
print(*s, sep='')
