Table of Contents
Hyper Strings – 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++ Hyper Strings HackerRank Solution
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
using namespace std;
#define ll long long int
vector<string> vs , distr;
map<string , int > mp;
void f( string s , int &N ) {
if( mp[s] ) return;
mp[s] = 1;
char ch = s[s.size()-1];
for( int i = 0; i < N; i++ ) {
if( vs[i][0] > ch ) f( s+vs[i] , N );
}
distr.push_back(s);
}
long long int dp[200][12];
int DISTR;
long long int MOD = 1000000007;
long long int f1( int len , int lastchar ) {
if( len <= 0 ) return 1;
long long int &ret = dp[len][lastchar];
if( ret == -1ll ) {
ret = 0ll;
for( int i = 0; i < DISTR; i++ ) {
int tsz = distr[i].size();
int fs = distr[i][0]-'a' , ls = distr[i][tsz-1]-'a';
if( (tsz <= len) && (fs) <= lastchar ) ret += f1( len-tsz , ls );
ret %= MOD;
}
}
return ret;
}
int main () {
int N , L;mp.clear();
scanf("%d %d" , &N , &L );
for( int i = 0; i < N; i++ ) {
string s; cin >> s;
vs.push_back(s);
}
f( "" , N );
int sz = distr.size()-1;
distr.resize(sz);DISTR = sz;
sort( distr.begin() , distr.end() );
/* cout << DISTR << "\n";
for( int i = 0; i < DISTR; i++ ) cout << distr[i] << "\n";
*/
memset( dp , -1 , sizeof(dp) );
ll ans = 0;
for( int i = 0; i <= L; i++ ) {
ans += f1( i , 11 );
ans %= MOD;
}
cout << ans << "\n";
return 0;
}
Java Hyper Strings HackerRank Solution
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class Solution {
static class Foo52 {
static final int MOD = 1000000007;
String[] arr;
int N;
int M;
String[] pat;
ArrayList<String>[] endXpat;
void main() {
BufferedReader br = null;
try {
br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().trim().split(" ");
N = Integer.parseInt(s[0].trim());
M = Integer.parseInt(s[1].trim());
arr = new String[N];
int count = 0;
for (int i = 0; i < N; i++) {
String str = br.readLine().trim();
if (str.length() == 0)
continue; // empty string will not be added
arr[count++] = str;
}
if (count != N) {
N = count;
arr = Arrays.copyOf(arr, N);
}
fillSet();
int res = doit();
System.out.println(res);
} catch (Exception e) {
e.printStackTrace();
} finally {
if (br != null) {
try { br.close(); } catch (Exception e) { e.printStackTrace(); }
}
}
}
/*
* dp[m,p] = dp3[m-len(p),v'] | v' = p.first char
* dp2[m,v] = sum { dp[m,p] | p ends with v}
* dp3[m,v] = sum {dp2[m,v'] | v' >= v}
*/
int doit() {
// seems that pat number should not be a lot, so no optimization is done on it
int size = pat.length;
int[][] dp = new int[M+1][size];
int[][] dp2 = new int[M+1][10];
int[][] dp3 = new int[M+1][10];
Arrays.fill(dp3[0], 1);
for (int m = 1; m <= M; m++) {
for (int i = 0; i < size; i++) {
if (pat[i].length() > m)
continue;
String curr = pat[i];
dp[m][i] = dp3[m-curr.length()][curr.charAt(0)-'a'];
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < size; j++) {
String curr = pat[j];
if (curr.charAt(curr.length()-1)-'a' == i)
dp2[m][i] = (dp2[m][i] + dp[m][j]) % MOD;
}
}
for (int i = 0; i < 10; i++) {
for (int j = i; j < 10; j++) {
dp3[m][i] = (dp3[m][i] + dp2[m][j]) % MOD;
}
}
}
int res = 0;
for (int m = 0; m <= M; m++) {
res = (res + dp3[m][0]) % MOD;
}
return res;
}
void fillSet() {
Arrays.sort(arr);
TreeSet<String> set = new TreeSet<String>();
set.add("");
char[] store = new char[10];
for (int len = 1; len <= 10; len++) {
fillSet(store, 0, 'a'-1, len, set);
}
set.remove("");
int n = set.size();
pat = new String[n];
int index = 0;
for (String str : set)
pat[index++] = str;
endXpat = new ArrayList[10];
for (int i = 0; i < 10; i++) {
endXpat[i] = new ArrayList<String>();
}
for (String str : pat) {
endXpat[str.charAt(str.length()-1)-'a'].add(str);
}
}
void fillSet(char[] store, int index, int last, int len, TreeSet<String> set) {
if (index == len) {
String curr = new String(Arrays.copyOf(store, len));
// check if curr ok
for (String pre : arr) {
if (pre.length() <= curr.length() && curr.indexOf(pre) == 0
&& set.contains(curr.substring(pre.length()))) {
set.add(curr);
break;
}
}
return;
}
for (int i = last+1; i <= 'j'; i++) {
store[index] = (char)i;
fillSet(store, index+1, i, len, set);
}
}
}
public static void main(String[] args) {
Foo52 foo = new Foo52();
foo.main();
}
}
Python 3 Hyper Strings HackerRank Solution
from collections import Counter
j,k = map(int, input().split())
supers_list = []
for i in range(j):
supers_list.append(input())
def check_concat(Str_, Sub_Str_):
if Sub_Str_ == "":
return False
for i in supers_list:
if i == Sub_Str_ and Str_ != Sub_Str_:
return True
x = Sub_Str_.startswith(i)
if x == True:
if check_concat(Str_, Sub_Str_[len(i):]) == True:
return True
return False
def filter_():
tmp = []
global supers_list
for i in supers_list:
if check_concat(i,i) == False:
tmp.append(i)
supers_list = tmp
filter_()
y = Counter(len(i) for i in supers_list)
saved = {}
def f(x):
if x in saved: return saved[x]
if x<1: return 0
k = y[x] if x in y else 0
for i in y:
k += y[i]*f(x-i)
saved[x] = k
return k
x = 0
for i in range(1,k+1):
x+=f(i)
print((x+1)%1000000007)
Python 2 Hyper Strings HackerRank Solution
N,M = map(int,raw_input().split())
SS = set()
def addSS(s):
if len(s)==0: return
if s in SS: return
SS.add(s)
for x in list(SS):
if x[-1]<s[0]: addSS(x+s)
if s[-1]<x[0]: addSS(s+x)
for i in xrange(N): addSS(raw_input().strip())
F = {}
def f(i,c):
if i>M: return 0
if (i,c) not in F:
F[i,c] = (1+sum(f(i+len(s),s[-1]) for s in SS if s[0]<=c))%1000000007
return F[i,c]
print f(0,'k')
C Hyper Strings HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#define P 1000000007
char s[1000];
long long h[2000][4],t,v[110][110][12],a[10000],zac,kon,b[2000],i,j,k,l,m,n,c[20][20][20];
void pridaj(long long mam)
{
long long jj,kk;
if(b[mam]) return;
b[mam]=1;
kk=1<<11;
while(((kk/2)&mam)==0) kk/=2;
//printf("mam %lld kk %lld\n",mam,kk);
for(jj=0;jj<n;jj++)
if((a[jj]&(kk-1))==0)
pridaj(mam+a[jj]);
return;
}
int main()
{
scanf("%lld %lld\n",&n,&m);
for(i=0;i<n;i++)
{
scanf("%s\n",s);
j=0;
a[i]=0;
while(s[j])
{
a[i] += (1<<(s[j]-'a'));
j++;
}
}
for(i=0;i<n;i++) pridaj(a[i]);
//m=0;
//for(i=0;i<(1<<10);i++)
// {
// if(b[i]) printf("%lld: %lld\n",i,b[i]);
//m++;
// }
//printf("%lld=m\n",m);
//return 0;
//m=0;
for(i=0;i<(1<<10);i++)
if(b[i])
{
zac=0;
while(((1<<zac)&i)==0) zac++;
kon=12;
while(((1<<kon)&i)==0) kon--;
l=0;
for(j=0;j<=12;j++) if(i&(1<<j)) l++;
// if(l==3) m++;
c[zac][kon][l]++;
}
//printf("..%lld=m\n",m);
//return 0;
/*
m=0;
for(i=0;i<12;i++)
for(j=0;j<12;j++)
for(l=0;l<12;l++)
if(l==3 && c[i][j][l])
{
printf("-- %lld %lld %lld -> %lld\n",i,j,l,c[i][j][l]);
m+=c[i][j][l];
}
printf("%lld\n",m);
return;
*/
k=0;
for(i=0;i<12;i++)
for(j=0;j<12;j++)
for(l=0;l<12;l++)
if(c[i][j][l])
{
h[k][0] = i;
h[k][1] = j;
h[k][2] = l;
h[k][3] = c[i][j][l];
k++;
}
v[0][0][9] = 1;
for(i=0;i<=m;i++)//zlom
for(l=0;l<=m;l++) //dlz
for(t=0;t<k;t++)
for(j=h[t][0];j<10;j++) //kon
if(l+h[t][2]<=m)
v[i+1][l+h[t][2]][h[t][1]] = (v[i+1][l+h[t][2]][h[t][1]]+h[t][3]*v[i][l][j])%P;
k=0;
for(i=0;i<=m;i++)
for(l=0;l<=m;l++)
for(j=0;j<10;j++)
//if(v[i][l][j]) printf("v %lld %lld %lld -> %lld\n",i,l,j,v[i][l][j]);
k = (k+v[i][l][j])%P;
printf("%lld\n",(k+P)%P);
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
