Weighted Uniform Strings – HackerRank Solution

In this post, we will solve Weighted Uniform Strings HackerRank Solution. This problem (Weighted Uniform Strings) is a part of HackerRank Problem Solving series.

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`.

Note:Â TheÂ âˆˆÂ symbol denotes thatÂ x[i]Â is anÂ element ofÂ set U.

Example

s = ‘abbcccdddd’
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Â sÂ that may or may not exist.

Constraints

• 1 <= lengthofs, n <= 105
• 1 <= queries[i] <= 107
• 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``````

Explanation 0

The weights of every possibleÂ uniform substringÂ in the stringÂ `abccddde`Â are shown below:

We printÂ `Yes`Â on the first four lines because the first four queries match weights of uniform substrings ofÂ s. We printÂ `No`Â for the last two queries because there are no uniform substrings inÂ sÂ that have those weights.

Note that whileÂ `de`Â is a substring ofÂ sÂ that would have a weight ofÂ 9, it isÂ not a uniform substring.

Note that we are only dealing with contiguous substrings. So `ccc` is not a substring of the string `ccxxc`.

Sample Input 1

``````aaabbbbcccddd
5
9
7
8
12
5``````

Sample Output 1

``````Yes
No
Yes
Yes
No``````

Solution – Weighted Uniform Strings – HackerRank Solution

C++

```#include <set>
#include <string>
#include <iostream>

static int weight(const char& c);

int main(){

std::string str;
std::cin >> str;

std::set<int> values;
for (size_t i = 0, j; i < str.length(); i = j) {
char last = str[i];
int last_w = 0;

for (j = i; j < str.length() && str[j] == last; ++j) {
last_w += weight(last);
values.insert(last_w);
}
}

int q, tmp;
std::cin >> q;

while (q --> 0) {
std::cin >> tmp;
std::cout << (values.find(tmp) == values.end() ? "No" : "Yes") << '\n';
}

return 0;
}

static int weight(const char& c) {
return c - 'a' + 1;
}
```

Python

```import sys
import string

symbols = string.ascii_lowercase

def gen_uniforms(s):
uniforms = {}

mult = 1
let_prev = ''
for let in s:
if let == let_prev:
mult += 1
else:
mult = 1

let_prev = let
uniforms[((symbols.index(let) + 1)*mult)] = True

return uniforms

if __name__ == "__main__":
s = input().strip()
n = int(input().strip())
uniforms = gen_uniforms(s)

for a0 in range(n):
x = int(input().strip())

if x in uniforms:
print("Yes")
else:
print("No")
```

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 n = in.nextInt();

//Build a set of weights
Set<Integer> weights = new HashSet<>();

int currentWeight = 0;
char prevLetter = ' ';
for(char letter : s.toCharArray())
{
if(letter != prevLetter)
currentWeight = letter - 'a' + 1;
else
currentWeight += letter - 'a' + 1;

prevLetter = letter;
}

for(int a0 = 0; a0 < n; a0++){
int x = in.nextInt();

if(weights.contains(x))
System.out.println("Yes");
else
System.out.println("No");
}
}
}
```

Note: This problem (Weighted Uniform Strings) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.