Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerRank Hyper Strings problem solution

YASH PAL, 31 July 2024

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.

HackerRank Hyper Strings problem solution

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 hyper_end in H_graded[letter]:
            letter_graded[letter].add(hyper_end)
            for mid in letters:
                if mid == hyper_end[0]:
                    break
                to_add = [hyper_beg + hyper_end for hyper_beg in letter_graded[mid]]  
                if to_add:
                    letter_graded[letter].update(to_add)
    
    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):
        for letter, graded in letter_graded.items():
            for supstr in graded:
                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) {
            int alz = Integer.numberOfLeadingZeros(a[k]);
            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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

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

        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("%dn",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* readline();
char** split_string(char*, int*);

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

    int masks[1024];
    int masklow[1024];
    int maskhigh[1024];
    int maskbits[1024];
    masks[0] = 1;
    for(int i = 1; i < 1024; i++){
        masks[i] = 0;
        for(int j = 0; j < n; j++){
            if((i&basicmasks[j]) == basicmasks[j] && (i - basicmasks[j]) < (1<<low[j]) && masks[i - basicmasks[j]] == 1){
                masks[i] = 1;
            }
        }
        maskhigh[i] = -1;
        masklow[i] = -1;
        maskbits[i] = 0;
        for(int j = 0; j < 10; j++){
            if(((i>>j)&1) == 1){
                maskhigh[i] = j;
                if(masklow[i] == -1){
                    masklow[i] = j;
                }
                maskbits[i]++;
            }
        }
    }

    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++){
                    currnum[i][maskhigh[j]] = (currnum[i][maskhigh[j]] + currnum[prevlen][k])%MOD;
                }
            }
        }
    }

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

}

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

    int temp;
    char** nm = split_string(readline(), &temp);

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

    if (n_endptr == n_str || *n_endptr != '') { 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 != '') { exit(EXIT_FAILURE); }

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

    for (int H_itr = 0; H_itr < n;) {
        int temp;
        char** itemlist = split_string(readline(), &temp);

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

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

    fprintf(fptr, "%dn", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    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] = '';
    }
    if(data[data_length - 1] != ''){
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '';
    }

    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}

algorithm coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes