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.

Task

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 <= 10⁵
• 1 <= queries[i] <= 10⁷
• 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;
            weights.add(currentWeight);
        }
        
        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.