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/
Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.