Hackerrank - Weighted Uniform Strings
A weighted string is a string of lowercase English letters where each letter has a weight. Character weights are to from to 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
anda
are uniform strings, butbcb
andcd
are not.
Given a string, , let be the set of weights for all possible uniform contiguous substrings of string . There will be queries to answer where each query consists of a single integer. Create a return array where for each query, the value is Yes
if . Otherwise, append No
.
Note: The symbol denotes that is an element of set .
Example
.
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 , 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 , the original string.
The second line contains an integer , the number of queries.
Each of the next lines contains an integer , the weight of a uniform subtring of that may or may not exist.
Constraints
- 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 . We print No
for the last two queries because there are no uniform substrings in that have those weights.
Note that while de
is a substring of that would have a weight of , 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
import java.io.*;import java.math.*;import java.security.*;import java.text.*;import java.util.*;import java.util.concurrent.*;import java.util.function.*;import java.util.regex.*;import java.util.stream.*;import static java.util.stream.Collectors.joining;import static java.util.stream.Collectors.toList;
class Result {
public static List<String> weightedUniformStrings(String s, List<Integer> queries) { // System.out.println(queries); HashSet<Integer> weights = new HashSet<>(); List<String> res = new ArrayList<>(); int index = 0;
while (index < s.length()) { Character letter = s.charAt(index); int currentLetterWeights = 0;
while (s.charAt(index) == letter) { currentLetterWeights += (int) letter - 96; weights.add(currentLetterWeights); index++; if (index >= s.length()) { break; } } }
for (int query : queries) { if (weights.contains(query)) { res.add("Yes"); } else { res.add("No"); } }
return res;
}
}
public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String s = bufferedReader.readLine();
int queriesCount = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> queries = IntStream.range(0, queriesCount).mapToObj(i -> { try { return bufferedReader.readLine().replaceAll("\\s+$", ""); } catch (IOException ex) { throw new RuntimeException(ex); } }) .map(String::trim) .map(Integer::parseInt) .collect(toList());
List<String> result = Result.weightedUniformStrings(s, queries);
bufferedWriter.write( result.stream() .collect(joining("\n")) + "\n" );
bufferedReader.close(); bufferedWriter.close(); }}
Comments
Post a Comment