Hi Chefs,
I am not able to find the mistake in below python code, please help me.
Problem statement : Weighted Uniform Strings | HackerRank
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
Hello @anon73122115, @sikh_coder and @codingisez Thanks for the reply 
, 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.
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:
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 : Weighted Uniform Strings | HackerRank
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.
Ohh sorry, you have to unlock it, leave it, just implement it as follow:
- Add binary search function
- 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 
Thank you chefs @codingisez @anon73122115 @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 
1 Like