Home Strings [Hackerrank] – Weighted Uniform Strings

[Hackerrank] – Weighted Uniform Strings

by nikoo28
0 comment 9 minutes read

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.

abccddde
        

We start off by writing the weight of ‘a’

abccddde
1       

Since the next character has changed, just put the weight of the new character.

abccddde
12      

Again the next character has changed. So just write the weight of the new character.

abccddde
123     

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.

abccddde
1236    

The character has changed again. So we just write the weight of new character.

abccddde
12364   

The next character is same. So we add the weight of the next character to the previous cell

abccddde
123648  

Again, the next character is same

abccddde
12364812 

The next character is different and hence we just write the weight of the new character.

abccddde
123648125

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.

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More