Let us try to simplify the problem as much as we can. We are given with some of the terms.
Weights:- According to the problem each character in the English alphabet has been assigned a weight. ‘a’ has been given a weight of 1, ‘b’ has a weight of 2, and so on. The weight of ‘z’ is 26. All the letters are assumed to be lowercase for simplicity.
Weight of a string:- This is defined as the sum of all the characters in the string. Example if a string consists of the characters
abcd = a(1) + b(2) + c(3) + d(4) = 10
study = s(19) + t(20) + u(21) + d(4) + y(25) = 89
Uniform Strings:- Strings with only one type of characters are termed as ‘uniform strings’. Some examples of uniform strings are ‘aaaa’, ‘bbbbbb’, ‘c’
Input String: A sample input string is given as ‘abccddde‘
It has the following contiguous uniform strings and weights
a = a(1) = 1
b = b(2) = 2
c = c(3) = 3
cc = c(3) + c(3) = 6
d = d(4) = 4
dd = d(4) + d(4) = 8
ddd = d(4) + d(4) + d(4) = 12
e = e(5) = 5
Thus we get the following weights {1, 2, 3, 6, 4, 8, 12, 5}
We are given a set U with some values. If a value can be formed by the weight of any uniform substring, the answer is ‘Yes’ else the answer is ‘No’
SOLUTION:
To start off with the problem, it is evident that we need to somehow find all the possible uniform strings in the given input string. But using a brute force approach would take a lot of time. A dynamic solution should be able to give the sum of a string at a constant time. A general approach in dynamic array is to create an array and keep on solving the problem successively.
Let us suppose we take an array equal to the size of the string.
| a | b | c | c | d | d | d | e |
We start off by writing the weight of ‘a’
| a | b | c | c | d | d | d | e |
| 1 |
Since the next character has changed, just put the weight of the new character.
| a | b | c | c | d | d | d | e |
| 1 | 2 |
Again the next character has changed. So just write the weight of the new character.
| a | b | c | c | d | d | d | e |
| 1 | 2 | 3 |
Now the next character is same. So we add the new weight to the weight of the previous cell. This ensures that we are having a sum of the contiguous string.
| a | b | c | c | d | d | d | e |
| 1 | 2 | 3 | 6 |
The character has changed again. So we just write the weight of new character.
| a | b | c | c | d | d | d | e |
| 1 | 2 | 3 | 6 | 4 |
The next character is same. So we add the weight of the next character to the previous cell
| a | b | c | c | d | d | d | e |
| 1 | 2 | 3 | 6 | 4 | 8 |
Again, the next character is same
| a | b | c | c | d | d | d | e |
| 1 | 2 | 3 | 6 | 4 | 8 | 12 |
The next character is different and hence we just write the weight of the new character.
| a | b | c | c | d | d | d | e |
| 1 | 2 | 3 | 6 | 4 | 8 | 12 | 5 |
Now in this array, we have all the possible weights of all the uniform strings that can be formed. Now we just need to seek the elements of the input set U. If any query does not belong in this array, then our answer will be “No”, else our answer will be “Yes.”
Here in an implementation of the above algorithm.
class UniformWeights {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
int n = in.nextInt();
Set<Integer> sumList = new HashSet<>();
char prev = s.charAt(0);
sumList.add(prev - 'a' + 1);
int sum = prev - 'a' + 1;
for (int i = 1; i < s.length(); i++) {
char next = s.charAt(i);
if (next == prev) {
sum += (prev - 'a' +1);
sumList.add(sum);
} else {
sumList.add(next - 'a' + 1);
prev = next;
sum = prev - 'a' + 1;
}
}
for (int a0 = 0; a0 < n; a0++) {
int x = in.nextInt();
if (sumList.contains(x))
System.out.println("Yes");
else
System.out.println("No");
}
}
}
Code language: Java (java)A working implementation of the code can be found here.
This problem can be found at HACKERRANK here.