# Yet Another KMP Problem

### Problem Statement :

```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].

Here is an implementation example of KMP:

kmp = 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;
}
}
Given a sequence x1,x2,...,x26, construct a string, S, that meets the following conditions:

1.The frequency of letter 'a' in S is exactly x1, the frequency of letter 'b' in S is exactly x2, and so on.
Let's assume characters of S are numbered from 1 to N, where Σxi = N. We apply the KMP algorithm to S and get a table, kmp[i], of size N. You must ensure that the sum of kmp[i] for all i is minimal.
If there are multiple strings which fulfill the above conditions, print the lexicographically smallest one.

Input Format

A single line containing 26 space-separated integers describing sequence x.

Constraints

The sum of all xi will be a positive integer <= 10^6.```

### Solution :

```                            ```Solution in C :

In C++ :

#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;

const int NMAX=1000005;

int n,fr;
char s[NMAX];

int main()
{
int i,j,mn,poz,cnt=0,ok;
//  freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
cin.sync_with_stdio(false);
mn=1<<30;
for (i=1;i<=26;i++)
{
cin>>fr[i];
n+=fr[i];
if (fr[i]<mn && fr[i]>0)
{
mn=min(mn,fr[i]);
poz=i;
}
if (fr[i]>0) cnt++;
}

if (cnt==1)
{
for (i=1;i<=n;i++) s[i]=poz+'a'-1;
cout<<(s+1)<<"\n";
return 0;
}
for (i=1;i<=n;i++) s[i]='>';
s=poz+'a'-1;
fr[poz]--;

ok=0;
for (j=1;j<=26 && !ok;j++)
if (fr[j]>0)
{
fr[j]--;
s=j+'a'-1;
ok=1;
}
i=3;
if (s==s)//a 3-a neaparat diferita
{
i=4;
while (fr[poz])
{
s[i]=poz+'a'-1;
fr[poz]--;
i+=2;
}
cnt=0;
for (i=1;i<=26;i++) cnt+=fr[i];
i=1;j=1;
while (cnt)
{
while (s[i]!='>') i++;
while (fr[j]==0) j++;
s[i]=j+'a'-1;fr[j]--;
cnt--;
}
}
else
{
i=3;
for (j=1;j<=26;j++)
while (fr[j])
{
s[i]=j+'a'-1;
fr[j]--;
i++;
}
}
cout<<(s+1)<<"\n";
return 0;
}

In Java :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static int[] readIntArray3(Scanner in, int size) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = in.nextInt();
}
return arr;
}

public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
int cases = 1;//in.nextInt();
for (int testcase = 0; testcase < cases; testcase++) {
kmpproblem(arr);
}
}

public static void kmpproblem(int[] arr) {
int least = Integer.MAX_VALUE;
int leastIndex = -1;
int smallestIndex = -1;
for (int i = 0; i < 26; i++) {
if (arr[i] < least && arr[i] > 0) {
least = arr[i];
leastIndex = i;
}
if (smallestIndex == -1 && arr[i] > 0) {
smallestIndex = i;
}
}
//        System.out.println(leastIndex + ": " + least);
//        System.out.println(smallestIndex);
if (leastIndex == -1)  {
System.out.println("");
return;
}
if (smallestIndex != leastIndex) {
System.out.print((char)(leastIndex+'a'));
arr[leastIndex]--;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < arr[i]; j++) {
System.out.print((char)(i+'a'));
}
}
return;
}
System.out.print((char)(leastIndex+'a'));
arr[leastIndex]--;
for (int i = leastIndex+1; i < 26; i++) {
for (int j = 0; j < arr[i]; j++) {
if (arr[leastIndex] > 0) {
System.out.print((char)(leastIndex+'a'));
arr[leastIndex]--;
}
System.out.print((char)(i+'a'));
}
}
while (arr[leastIndex] > 0) {
System.out.print((char)(leastIndex+'a'));
arr[leastIndex]--;
}

}
}

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
int letter = 0, min=26, first = -1;
int data;
data=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);
}
}
}

return 0;
}

In Python3 :

from string import ascii_lowercase as A
import sys
x = list(map(int, input().split()))
used = [i for i in range(26) if x[i]]
if len(used) == 0:
sys.exit()
if len(used) == 1:
print(A[used] * x[used])
else:
f = min(used, key=lambda a: (x[a], a))
used = [a for a in used if a != f]
if x[f] == 1:
print(A[f] + ''.join(A[c]*x[c] for c in used))
elif f > used:
x[f] -= 1
print(A[f] + ''.join(A[c]*x[c] for c in range(26)))
elif 2*(x[f]-2) <= sum(x)-2:
res = 2*A[f]
b = ''.join(A[c]*x[c] for c in used)
x[f] -= 2
i = 0
while x[f]:
res += b[i] + A[f]
i += 1
x[f] -= 1
res += b[i:]
print(res)
else:
x[f] -= 1
x[used] -= 1
print(A[f] + A[used] + A[f]*x[f] + ''.join(A[c]*x[c] for c in used))```
```

## View More Similar Problems

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

## Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing