# HackerRank Hyper Strings problem solution

In this HackerRank Hyper Strings problem solution, we have given a set of Super Strings H, a Hyper String is a string that can be constructed by concatenation of some Super Strings of the set H. We can use each Super String as many times as we want. Given set H, you have to compute the number of Hyper Strings with a length no greater than M.

## Problem solution in Python.

```#!/bin/python3

import os
import sys

#
# Complete the hyperStrings function below.
#
def hyperStrings(m, H):
modul = 10 ** 9 + 7
letters = "abcdefghij"
H = [hyperstr for hyperstr in H if len(hyperstr) > 0]

H_graded = {letter: [hyper_str for hyper_str in H if hyper_str[-1] == letter] for letter in letters}
letter_graded = {letter : set() for letter in letters}
for letter in letters:
for mid in letters:
if mid == hyper_end[0]:
break

dp = [{letter: 0 for letter in letters} for length in range(m+1)]
dp[0] = {letter: 1 for letter in letters}
for length in range(1, m+1):
if length < len(supstr):
continue
dp[length][letter] = (dp[length][letter] + dp[length - len(supstr)][supstr[0]]) % modul
for index in range(len(letters) - 1, 0, -1):
dp[length][letters[index - 1]] = (dp[length][letters[index - 1]] + dp[length][letters[index]]) % modul
return sum([dp[length]['a'] for length in range(m + 1)]) % modul

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nm = input().split()
n = int(nm[0])
m = int(nm[1])
H = []
while len(H) < n:
H_item = input().split()
H = H + H_item

result = hyperStrings(m, H)
fptr.write(str(result) + '\n')
fptr.close()
```

{"mode":"full","isActive":false}

## Problem solution in Java.

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

public class Solution {

static final int AB = 10;
static final int MAX = 1 << AB;
static final long MOD = 1_000_000_007;

static long hyperStrings(int m, int[] arr) {
Arrays.sort(arr);
boolean[] b = new boolean[MAX];
b[0] = true;
for (int i = 0; i < arr.length; i++) {
int n = 1 << Integer.numberOfTrailingZeros(arr[i]);
for (int j = n-1; j >= 0; j--) {
if (b[j]) {
b[j | arr[i]] = true;
}
}
}
int[] a = new int[MAX];
int n = 0;
for (int i = 0; i < MAX; i++) {
if (b[i]) {
a[n++] = i;
}
}

long result = 0;

int[][] s = new int[a.length+1][AB];
s[0][AB-1] = 1;
for (int i = 0; i < m+1; i++) {
for (int j = 0; j < AB; j++) {
result = (result + s[i][j]) % MOD;
for (int k = 0; k < n; k++) {
int pop = Integer.bitCount(a[k]);
int atz = Integer.numberOfTrailingZeros(a[k]);
if ((i + pop) <= m && atz <= j) {
s[i+pop][31 - alz] = (int)((s[i+pop][31 - alz] + s[i][j]) % MOD);
}
}
}
}
return result;
}

static void load(int[] a, int i, char[] arr) {
for (char c : arr) {
a[i] |= 1 << (c - 'a');
}
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());

int[] a = new int[n];
if (s.contains(" ")) {
String[] v = s.split(" ");
for (int i = 0; i < n; i++) {
}
} else {
for (int i = 1; i < n; i++) {
}
}

long result = hyperStrings(m, a);

bw.write(String.valueOf(result));
bw.newLine();

br.close();
bw.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<cstdio>
#define REST 1000000007
char S[1000];
int N,M;
char nr[110][110];
int len[110],sol[110];
int lung(char S[100]){
int x=0;
while('a'<=S[x] && S[x]<='z')
++x;
return x;
}
int check(int s1, int poz, int s2){
if(poz+len[s2]-1>len[s1])
return 0;
int k;
for(k=0;k<len[s2];++k){
if(nr[s1][poz+k]!=nr[s2][k+1])
return 0;
}
return 1;
}
void reduc(){
int i,j,k;
char ax[110];
for(i=1;i<=N;++i){
if(len[i]==110)
continue;
for(j=0;j<=len[i];++j)
ax[j]=0;
ax[0]=1;
for(j=1;j<=len[i];++j){
if(!ax[j-1])
continue;
for(k=1;k<=N;++k){
if(k==i || len[k]==110)
continue;
if(check(i,j,k))
ax[j+len[k]-1]=1;
}
}
if(ax[len[i]])
len[i]=110;
}
}
int main(){
int i,j;
scanf("%d%d",&N,&M);
for(i=1;i<=N;++i){
scanf("%s",nr[i]+1);
len[i]=lung(nr[i]+1);
}
reduc();
sol[0]=1;
for(i=0;i<=M;++i){
for(j=1;j<=N;++j){
if(i+len[j]>M)
continue;
sol[i+len[j]]+=sol[i];
if(sol[i+len[j]]>=REST)
sol[i+len[j]]-=REST;
}
}
for(i=1;i<=M;++i){
sol[0]+=sol[i];
if(sol[0]>=REST)
sol[0]-=REST;
}
printf("%d\n",sol[0]);
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007

char** split_string(char*, int*);

/*
* Complete the hyperStrings function below.
*/
int hyperStrings(int m, int n, char** H) {
int low[n];
for(int i = 0; i < n; i++){
low[i] = H[i][0] - 'a';
int len = strlen(H[i]);
for(int j = 0; j < len; j++){
}
}

for(int i = 1; i < 1024; i++){
for(int j = 0; j < n; j++){
}
}
for(int j = 0; j < 10; j++){
if(((i>>j)&1) == 1){
}
}
}
}

int currnum[m + 1][10];
for(int i = 0; i <= m; i++){
for(int j = 0; j < 10; j++){
currnum[i][j] = 0;
}
}
currnum[0][9] = 1;

for(int i = 1; i <= m; i++){
for(int j = 1; j < 1024; j++){
int prevlen = i - maskbits[j];
if(masks[j] == 1 && prevlen >= 0){
for(int k = masklow[j]; k < 10; k++){
}
}
}
}

int total = 0;
for(int i = 0; i <= m; i++){
for(int j = 0; j < 10; j++){
total = (total + currnum[i][j])%MOD;
}
}

}

int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

int temp;

char* n_endptr;
char* n_str = nm[0];
int n = strtol(n_str, &n_endptr, 10);

if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

char* m_endptr;
char* m_str = nm[1];
int m = strtol(m_str, &m_endptr, 10);

if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }

char** H = malloc(n * sizeof(char*));

for (int H_itr = 0; H_itr < n;) {
int temp;

for(int i = 0; i < temp; i++){
*(H + H_itr) = itemlist[i];
H_itr++;
}
}

int result = hyperStrings(m, n, H);

fprintf(fptr, "%d\n", result);

fclose(fptr);

return 0;
}

size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);

while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);

if (!line) { break; }

data_length += strlen(cursor);

if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

size_t new_length = alloc_length << 1;
data = realloc(data, new_length);

if (!data) { break; }

alloc_length = new_length;
}

if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
if(data[data_length - 1] != '\0'){
data_length++;
data = realloc(data, data_length);
data[data_length - 1] = '\0';
}

data = realloc(data, data_length);

return data;
}

char** split_string(char* str, int* num) {
char** splits = NULL;
char* token = strtok(str, " ");

int spaces = 0;

while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}

splits[spaces - 1] = token;

token = strtok(NULL, " ");
}
*num = spaces;

return splits;
}
```

{"mode":"full","isActive":false}