Weighted Uniform Strings HackerRank Solution in C, C++, Java, Python

A weighted string is a string of lowercase English letters where each letter has a weight. Character weights are 1 to 26 from a to z as shown below:

  • The weight of a string is the sum of the weights of its characters. For example:
  • A uniform string consists of a single character repeated zero or more times. For example, ccc and a are uniform strings, but bcb and cd are not.

Given a string,s , let U be the set of weights for all possible uniform contiguous substrings of string s. There will be n queries to answer where each query consists of a single integer. Create a return array where for each query, the value is Yes if query[i]=U. Otherwise, append No.

Example

s=’abbcccddddd’

.queries = [1,7,5,4,15]

Working from left to right, weights that exist are:

string  weight

a       1

b       2

bb      4

c       3

cc      6

ccc     9

d       4

dd      8

ddd     12

dddd    16

 

Now for each value in queries, see if it exists in the possible string weights. The return array is [‘Yes’, ‘No’, ‘No’, ‘Yes’, ‘No’].

Function Description

Complete the weightedUniformStrings function in the editor below.

weightedUniformStrings has the following parameter(s):

– string s: a string

– int queries[n]: an array of integers

Returns

– string[n]: an array of strings that answer the queries

Input Format

The first line contains a string s, the original string.

The second line contains an integer n, the number of queries.

Each of the next n lines contains an integer queries[i], the weight of a uniform subtring of  that may or may not exist.

Constraints

  • 1<=lengthofs,n<=10^5
  • 1<=queries[i]<=10^7
  •  S will only contain lowercase English letters, ascii[a-z].

Sample Input 0

abccddde

6

1

3

12

5

9

10

 

Sample Output 0

Yes

Yes

Yes

Yes

No

No

 

Weighted Uniform Strings HackerRank Solution in C

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    char* s = (char *)malloc(512000 * sizeof(char));
    int *c = (int *)calloc(sizeof(int), 200);
    int *value = (int *)calloc(sizeof(int), 10000001);
    scanf("%s",s);
    int n, cnt = 0; 
    for(int i = 0; s[i] != '\0'; i++){
        value[s[i] - 'a' + 1] = 1;
        cnt = s[i] - 'a' + 1;
        while(s[i + 1] != '\0' && s[i] == s[i + 1]){
            cnt += s[i] - 'a' + 1;
            value[cnt] = 1;
            i++;
        }
    }
    scanf("%d",&n);
    for(int a0 = 0; a0 < n; a0++){
        int x, i; 
        scanf("%d",&x);
        if (value[x]){
            printf("Yes\n");
        }
        else printf("No\n");
        // your code goes here
    }
    return 0;
}

 

Weighted Uniform Strings HackerRank Solution in C++

//    Mohib Manva
#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
#define LOCAL 0
#define pb push_back
#define ll long long

ll po(ll a,ll b){
    ll x = 1,y=a;
    while(b>0){
        if(b%2){
            x = x*y;
            x %= mod;
        }
        y=y*y;
        y%=mod;
        b/=2;
    }
    return x;
}

int main(){
    if(LOCAL){
        freopen("C:/Users/gold/Desktop/sublime IO/input.txt","r",stdin);
        freopen("C:/Users/gold/Desktop/sublime IO/output.txt","w",stdout);
    }
    int T = 1;
    //scanf("%d",&T);
    string s;
    cin>>s;
    int n = s.length();
    map<int,bool> dp;
    for(int i=0;i<n;i++){
        int j = i;
        int sum = 0;
        while(j<n&&s[j]==s[i]){
            sum += s[i]-'a'+1;
            dp[sum] = 1;
            j++;
        }
        int cnt = j - i;
        dp[(cnt)*(s[i]-'a'+1)] = 1;
        i = j-1;
    }
    cin>>T;
    while(T--){
        int x;
        cin>>x;
        puts(dp[x]?"Yes":"No");
    }
    return 0;    
}

 

Weighted Uniform Strings HackerRank Solution in Java

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int len =  s.length();
        int n = in.nextInt();
        Set<Integer> set = new HashSet<Integer>();
        int i=0;
        while(i<len){
             int j=i;
             int sum =0;
             while( j<len && s.charAt(i)==s.charAt(j) ){
                 sum += (s.charAt(i)-'a') +1;
                 set.add(sum);
                 j++;
             }
            i = j;
        }
        for(int a0 = 0; a0 < n; a0++){
            int x = in.nextInt();
            if (set.contains(x)){
                System.out.println("Yes");
            }
            else{
                System.out.println("No");
            }
        }
    }
}

 

Weighted Uniform Strings HackerRank Solution in Python

#!/bin/python

import sys
di = {}
a = 'abcdefghijklmnopqrstuvwxyz'
for i in xrange(26):
    di[a[i]] = i+1
    
s = raw_input().strip()
hi = {}
pr = '*'
co = 0
for i in s:
    if i==pr:
        co += di[i]
        hi[co] = 1
    else:
        pr = i
        co = di[i]
        hi[co] = 1
        
n = int(raw_input().strip())
for a0 in xrange(n):
    x = int(raw_input().strip())
    if x in hi:
        print 'Yes'
    else:
        print 'No'

 

Weighted Uniform Strings HackerRank Solution in C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        string s = Console.ReadLine();
        int n = Convert.ToInt32(Console.ReadLine());
        
        var hash = new HashSet<int>();
        
        int weight = -1;
        int count = 0;
        foreach(var ch in s)
        {
            var w = ch-'a' + 1;
            if (weight != w)
            {
                weight = w;
                count = 0;
            }
            
            count++;
            hash.Add(weight*count);
        }
        
        
        for(int a0 = 0; a0 < n; a0++){
            int x = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine(hash.Contains(x) ? "Yes" : "No");
        }
    }
}

 

Attempt Weighted Uniform Strings HackerRank Challenge

Link – https://www.hackerrank.com/challenges/weighted-uniform-string/

Next HackerRank Challenge Solution 

Link – https://exploringbits.com/separate-the-numbers-hackerrank-solution/

 

Leave a Comment