Help in hackerrank problem

Hi Chefs,
I am not able to find the mistake in below python code, please help me.
Problem statement : https://www.hackerrank.com/challenges/weighted-uniform-string/problem

s = input()
weights = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6, "g":7, "h":8, "i":9, "j":10, "k":11, "l":12, "m":13, "n":14, "o":15, "p":16, "q":17, "r":18, "s":19, "t":20, "u":21, "v":22, "w":23, "x":24, "y":25, "z":26}
ws = []
for i in range(len(s)):
    if i == 0 and s[i] in weights:
        ws.append(weights[s[i]])
        continue
    if s[i]==s[i-1]:
        ws.append(ws[i-1]+weights[s[i]])
    else:
        ws.append(weights[s[i]])
n = int(input())
j = 0
found = -1
k = 0
while k<n:
    i=int(input())
    if j>=len(ws):
        print("No")
    while j<len(ws):
        #print(i,ws[j],j)
        if i==ws[j]:
            print("Yes")
            found=j
            j+=1
            break
        
        if j==len(ws)-1 and found==-1:
            j=0
            print("No")
            break
        elif j==len(ws)-1 and found!=0:
            j=found
            print("No")
            break
        else :
            j+=1
            continue
    k+=1

Can you tell your approach? As the code is in python i am not able to debug it.
The approach is: You have to traverse the string. when you are 0 index of string. just push the value
s[i]-‘a’+1 into the vector. After that start the loop from index 1 and go till the end of the string. And if s[i] == s[i-1], just push the value A[i-1] + s[i]-‘a’+1 into the vector otherwise simply push the value of s[i]-‘a’+1;
Now start taking the inputs.if you find the value given in the input answer is YES otherwise ans is NO.
Here,A is the name of the vector.
Hope you know about vector . It is just a dynamic array.

1 Like

Few points:

1.) I don’t understand what you are trying to do after reading queries, but here’s what you should do:

while k<n:
i=int(input())
if(ws.count(i)>0):
print(“Yes”)
else:
print(“No”)
k+=1

2.) Even by doing this, you won’t pass much of the test cases, coz it’s slow. So, you better use dictionary or maps(I don’t remember what we use in python for lookup), that way you could store the values as keys, and simply check if you have that value.

1 Like

Just use binary search for finding if element is in array ws.
https://www.hackerrank.com/challenges/weighted-uniform-string/submissions/code/112359488

1 Like

Hello @shubham97361, @sikh_coder and @codingisez Thanks for the reply :slight_smile: , sorry for the inconvenience in framing my question.

The approach what you said here : s[i]-‘a’+1 into the vector. After that start the loop from index 1 and go till the end of the string. And if s[i] == s[i-1], just push the value A[i-1] + s[i]-‘a’+1 into the vector otherwise simply push the value of s[i]-‘a’+1; (the following block is exactly doing that)

for i in range(len(s)):
    if i == 0 and s[i] in weights:
        ws.append(weights[s[i]])
        continue
    if s[i]==s[i-1]:
        ws.append(ws[i-1]+weights[s[i]])
    else:
        ws.append(weights[s[i]])

Then I have started taking inputs of queries in the following block of code and comparing the query with the values of the list formed in the above block of code and printing “Yes” on matching and “No” on not matching:

n = int(input())
j = 0
found = -1
k = 0
while k<n:
    i=int(input())
    if j>=len(ws):
        print("No")
    while j<len(ws):
        #print(i,ws[j],j)
        if i==ws[j]:
            print("Yes")
            found=j
            j+=1
            break
        
        if j==len(ws)-1 and found==-1:
            j=0
            print("No")
            break
        elif j==len(ws)-1 and found!=0:
            j=found
            print("No")
            break
        else :
            j+=1
            continue
    k+=1

In the above block I am taking the input query as per the problem statement and traversing through the list ws:
(1) If the query matches the value in list ws then printing “Yes” and noting that index as “found” then breaking the inner loop over here and continuing with outer loop for the next query and then traversing the inner loop from the index “found”.
(2) If the query didn’t match with any value in list ws till last index, then will print “No” for that particular query and then go ahead with the next query input and traverse it from the index “found” of the list ws.
For each and every input query as explained in the point (1) if it matches in the list ws then it prints “Yes” and moves to the next query, if it is not matching in the list ws as per the point (2) it prints “No” and moves further.

This is my approach, am I correct?? If not please correct me.

Thanks everyone in advance.

I am not able to see anything by https://www.hackerrank.com/challenges/weighted-uniform-string/submissions/code/112359488, I can see only blank page.

Make j=0 and found = -1 after taking i as input
(This approach which you are doing will give TLE , you can use binary search instead)

Sample Input

abccddde
6
1
3
12
5
9
10

Sample Output

Yes
Yes
Yes
Yes
No
No

Explanation

The weights of every possible uniform substring in the string abccddde are shown below:

image

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 .


I am wondering how will the binary search work on this explanation???
@balani_mohit and @codingisez

Problem statement can be found here : https://www.hackerrank.com/challenges/weighted-uniform-string/problem

After having your ws array, sort the array and for every input i , search if it is present in ws array or not using binary search.

Check my code here : https://ideone.com/WU7UMJ

1 Like

Ohh sorry, you have to unlock it, leave it, just implement it as follow:

  1. Add binary search function
  2. Then find if WS array contains required element or not
    3 if it does, it will return it’s index else -1, store it in found
    4 if found =-1, print No else Yes

What you are basically doing is, storing all elements in WS, till that it’s fine, later in query section, use binary search instead of whole part, below i=int(input ())
you are doing same before but using linear search with cancer conditions

from bisect import bisect_left 
  
def BinarySearch(a, x): 
    i = bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    else: 
        return -1


s = input()
weights = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6, "g":7, "h":8, "i":9, "j":10, "k":11, "l":12, "m":13, "n":14, "o":15, "p":16, "q":17, "r":18, "s":19, "t":20, "u":21, "v":22, "w":23, "x":24, "y":25, "z":26}
ws = []
for i in range(len(s)):
    if i == 0 and s[i] in weights:
        ws.append(weights[s[i]])
        continue
    if s[i]==s[i-1]:
        ws.append(ws[i-1]+weights[s[i]])
    else:
        ws.append(weights[s[i]])
# for i in range(len(ws)):
#     print(ws[i])

n = int(input())
j = 0
found = -1
k = 0
ws.sort()
while k<n:
    i=int(input())
    found=BinarySearch(ws,i)
    if(found==-1):
        print("No")
    else:
        print("Yes")
    
    # if j>=len(ws):
    #     print("No")
    # while j<len(ws):
    #     #print(i,ws[j],j)
    #     if i==ws[j]:
    #         print("Yes")
    #         found=j
    #         j+=1
    #         break
        
    #     if j==len(ws)-1 and found==-1:
    #         j=0
    #         print("No")
    #         break
    #     elif j==len(ws)-1 and found!=0:
    #         j=found
    #         print("No")
    #         break
    #     else :
    #         j+=1
    #         continue
    # j=0;
    # found=-1
    k+=1
1 Like

Your approach seems correct. I have done the same thing. You can use binary search to optimise your code but i have simply traversed the vector to find the element and it passed all the test cases so you may apply linear search.
There must be some error in implementing it,i guess. If you know c++, try implementing this approach on that and if you will get wrong answer,ask again.

1 Like

Awesome :upside_down_face: Thank you chefs @codingisez @shubham97361 @balani_mohit. Because of you guys I learnt a new module Bisect in python and you guys made my logic very simple. Thank you very much :blush:

1 Like