In this HackerRank Yet Another KMP problem solution we have given a sequence construct a string S. if there are multiple strings that fulfill the conditions print the lexicographically smallest one.
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='')
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; }