Hello Programmers, In this post, you will learn how to solve HackerRank Weighted Uniform Strings Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
HackerRank Weighted Uniform Strings Solution
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,
cccandaare uniform strings, butbcbandcdare 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
HackerRank Weighted Uniform Strings Solution
Weighted Uniform Strings 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));
scanf("%s",s);
int n;
scanf("%d",&n);
int *cnt = (int*)malloc(32 * sizeof(int));
for(int i=0;i<26;i++)cnt[i]=0;
int len = strlen(s);
int bef = 27, cont = 0;
for(int i=0;i<len;i++){
int id = s[i]-'a';
if(id!=bef){
bef=id;
cont=0;
}
cont++;
cnt[id]=fmax(cnt[id],cont);
}
for(int a0 = 0; a0 < n; a0++){
int x;
scanf("%d",&x);
// your code goes here
bool ok = false;
for(int c=0;c<26;c++){
int w = c+1;
if(x%w)continue;
if(x/w > cnt[c])continue;
ok=true;
break;
}
puts(ok?"Yes":"No");
}
return 0;
}Weighted Uniform Strings Solution in Cpp
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
bool reach[10000010];
int main(){
string s;
cin >> s;
int val = 0;
for (int i=0; i<s.size(); i++) {
if (i > 0 && s[i] != s[i-1]) val = 0;
val += (s[i]-'a'+1);
reach[val] = true;
}
int n;
cin >> n;
for(int a0 = 0; a0 < n; a0++){
int x;
cin >> x;
cout << (reach[x] ? "Yes\n" : "No\n");
}
return 0;
}Weighted Uniform Strings Solution in Java
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int[] distribution(String s) {
int[] ds = new int[26];
char ch = '\0';
int d = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c != ch) {
ch = c;
d = 1;
} else {
d++;
}
int j = (int)(c - 'a');
if(d > ds[j]) ds[j] = d;
}
return ds;
}
static int[] distribution2(String s) {
int[] ds = new int[26];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int j = (int)(c - 'a');
ds[j]++;
}
return ds;
}
static String contains(int n, int[] ds) {
for (int i = 0; i < ds.length; i++) {
int w = i + 1;
if(n % w == 0 && n / w <= ds[i]) return "Yes";
}
return "No";
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
int[] ds = distribution(s);
int n = in.nextInt();
for(int a0 = 0; a0 < n; a0++){
int x = in.nextInt();
System.out.println(contains(x, ds));
// your code goes here
}
}
}Weighted Uniform Strings 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 Solution using JavaScript
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
function main() {
var s = readLine();
var n = parseInt(readLine());
var u = {};
// build set of weights
var hi = 0;
var lo = 0;
var char = s.charAt(0);
u[getCharWeight(char)] = true;
while (++hi < s.length) {
if (s.charAt(hi) == char) {
var newWeight = getCharWeight(char)*(hi-lo+1);
if (u.hasOwnProperty(newWeight) == false)
u[newWeight] = true;
}
else {
char = s.charAt(hi);
lo = hi;
var newWeight = getCharWeight(char);
if (u.hasOwnProperty(newWeight) == false)
u[newWeight] = true;
}
}
// respond to queries
for(var a0 = 0; a0 < n; a0++){
var x = parseInt(readLine());
if (u.hasOwnProperty(x) == true)
console.log("Yes");
else
console.log("No");
}
}
function getCharWeight(char) {
return char.charCodeAt(0) - 96;
}Weighted Uniform Strings Solution in Scala
object Solution {
import scala.collection.mutable.BitSet
def main(args: Array[String]) {
val sc = new java.util.Scanner (System.in);
var s = sc.next();
var n = sc.nextInt();
var a0 = 0;
var b : BitSet = BitSet();
var sum = (s(0) - 'a') + 1;
b = b + sum;
for(i<-1 until s.length) {
if(s(i) == s(i - 1)) {
sum += (s(i) - 'a') + 1
b = b + sum // add to set
} else {
sum = (s(i) - 'a') + 1
b = b + sum // add to set
}
}
while(a0 < n){
var x = sc.nextInt();
// your code goes here
if(b.contains(x)) {
println("Yes")
} else {
println("No")
}
a0+=1;
}
}
}Weighted Uniform Strings Solution in Pascal
(* Enter your code here. Read input from STDIN. Print output to STDOUT *)
var s:ansistring;
n,i,j:longint;
l:array[0..100000]of longint;
a:array[0..10000000]of boolean;
begin
readln(s);
readln(n);
a[ord(s[1])-ord('a')+1]:=true;
l[1]:=1;
for i:=2 to length(s) do
begin
if s[i]=s[i-1] then l[i]:=l[i-1]+1 else l[i]:=1;
a[(ord(s[i])-ord('a')+1)*l[i]]:=true;
end;
for i:=1 to n do
begin
readln(j);
if a[j] then writeln('Yes') else writeln('No');
end;
end.
Disclaimer: This problem (Weighted Uniform Strings) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.