ProblemSolving

Hacker Rank Problem Weighted Uniform String Solution

A weighted string is a string of lowercase English letters where each letter has a weight in the inclusive range from to 26, defined below:

We define the following terms:

  • The weight of a string is the sum of the weights of all the string’s characters. For example:
    • Eg. abc =>1+2+3=6 ,java =>10+1+22+1=34 ,ccc =>3+3+3 =9, zzz => 26+26+26 =78
  • uniform string is a string consisting of a single character repeated zero or more times. For example, ccc and aare uniform strings, but bcb and cd are not (i.e., they consist of more than one distinct character).
  • Given a string ,s , let U be the set of weights for all possible uniform substrings (contiguous) of string . You have to answer n queries, where each query i consists of a single integer,x_i . For each query, print Yes on a new line if  x_i belongs to U (x_i  is an element of set U); otherwise, print No instead.

Input Format

The first line contains a string denoting s (the original string).
The second line contains an integer denoting  n(the number of queries).
Each line i of the n subsequent lines contains an integer denoting x_i (the weight of a uniform subtring of s that may or may not exist).

Constraints

  • 1<= length of String s, n<= 10^5
  • 1<= x_i <= 10^7
  • s  will only contain lowercase English letters.

Output Format

Print  lines. For each query, print Yes on a new line if x_i belongs U; otherwise, print No instead.

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  that have those weights.

Note that while de is a substring of  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.

There are two ways to implement the solution:

  1. Accepting int one by one each time calculating weight of substring and Then show final result.
  2. Getting all possible weight of substring added to HashSet and then check the input weight and show final result.

Solution 1:Solution1.java:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution1 {
        public static boolean weight_matches(int x,int sum_weight){
              if(x==sum_weight){
                  // System.out.println("Matches:"+x+" "+sum_weight);
                   return true;
             }else return false;
        }
 
        public static boolean chkstr(String s,int n){
            if(s.length()>=1 && s.length()<=Math.pow(10,5) && n>=1 && n<= Math.pow(10,5)){
              return true;
            }else return false;
        }

        public static void main(String[] args) {
             Scanner in = new Scanner(System.in);
             boolean moveon=false;
             String s="";
             int n =0;
             try{
                s = in.next(); 
                n = in.nextInt();
                if(chkstr(s,n)){
                     moveon=true;
                 }
             }catch(Exception execp){
                 moveon=false;
             }
 
             String final_Status="";
 
             for(int a0 = 0; a0 < n && moveon; a0++){
                 int x = in.nextInt();
                 char[] s_array=s.toCharArray();
                 int sum_weight=0;
                 char char_holder=s_array[0];
                 for(int i=0;i<s_array.length;i++){
 
                     if(s_array[i]==char_holder){
                         sum_weight=sum_weight+((int)char_holder-96);
                       //System.out.println(sum_weight);
                     }else if(s_array[i]!=char_holder){
                             char_holder=s_array[i];
                             sum_weight=0;
                             sum_weight=sum_weight+((int)char_holder-96);
                           //System.out.println(sum_weight);
                     }
 
                    if(weight_matches(x,sum_weight)){
                          final_Status="Yes";
                          break;
                     }else final_Status="No";
                 }
                 System.out.println(final_Status);
 
 // your code goes here
              }
     }
}

Solution 2: Solution2.java:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution2 {
       private static HashSet<Integer> getWeights(String str) {
               HashSet<Integer> weights = new HashSet<>();
               int weight = 0;
               char prev = ' '; // so it doesn't match 1st character
               for (int i = 0; i < str.length(); i++) {
                    char curr = str.charAt(i);
                    if (curr != prev) {
                       weight = 0;
                     } 
                   weight += curr - 'a' + 1;
                   weights.add(weight);
                   prev = curr;
               }    
               return weights;
       }

       public static void main(String[] args) {
              Scanner scan = new Scanner(System.in);
              String str = scan.next();
              int n = scan.nextInt();
              HashSet<Integer> weights = getWeights(str);
              while (n-- > 0) {
                   int x = scan.nextInt();
                   System.out.println(weights.contains(x) ? "Yes" : "No");
              }
             scan.close(); 
      }
}

Conclusion:

Solution 1 works fine but too long time for execution and can go timeout for large number of queries and big length strings.

Solution 2 works fine also it runs well at large number of queries and large length of substring.

Thank You.

One thought on “Hacker Rank Problem Weighted Uniform String Solution”

Leave a Reply

Your email address will not be published. Required fields are marked *