HackerRank Yet Another KMP problem solution

In this 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 i (where 1 <= i <= N) it calculates the largest l (where 0 <= l <= i-1) such that for every p (where 1 <= p <= l) there is S[p] = S[i – l + p].

we have given a sequence construct a string S. if there are multiple strings that fulfill the conditions print the lexicographically smallest one.

HackerRank Yet Another KMP problem solution in Python.

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='')

Yet Another KMP problem solution in Java.

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("", 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("",Character.toString(ch));
            s1=s1+s;
            ++ch;
        }
        System.out.println(s1);
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
typedef unsigned long long uint64;
typedef long long sint64;

uint v[26];

char s[1000005];
uint sn;

int main(int argc, char* argv[])
{
	uint n = 26;

	for (uint i = 0; i < n; ++i)
		cin >> v[i];

	uint mi = 0;
	for (uint i = 0; i < 26; ++i)
	{
		if (v[i])
		{
			mi = i;
			break;
		}
	}

	uint mmi = mi;
	for (uint i = mi + 1; i < 26; ++i)
	{
		if (v[i] && v[i] < v[mmi])
			mmi = i;
	}

	s[sn++] = mmi + 'a';
	--v[mmi];
	if (mmi == mi)
	{
		for (uint i = mi + 1; i < 26; ++i)
		{
			if (v[i])
			{
				mmi = i;
				break;
			}
		}

		if (mi != mmi)
		{
			for (uint i = 0; i < v[mi]; ++i)
			{
				s[sn++] = mi + 'a';
				s[sn++] = mmi + 'a';
				--v[mmi];
			}
			v[mi] = 0;
		}
	}

	for (uint j = 0; j < 26; ++j)
	{
		for (uint i = 0; i < v[j]; ++i)
			s[sn++] = j + 'a';
	}

	cout << s << endl;
	return 0;
}

Problem solution in C.

#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;
}