The "Save Humanity" problem on Hackerrank asks us to:
... find all substrings in the patient DNA that either exactly matches the virus DNA, or has at most one mismatch.
For example:
"aa"
and"aa"
are matching,"ab"
and"aa"
are matching, while"ab"
and"ba"
are not.Input Format
The first line contains the number of test cases T. T test cases follow. Each case contains two strings P(Patient DNA) and V(Virus DNA) separated by space.
Output Format
Output T lines, one corresponding to each test case. For each test case, output a space delimited list of starting indices (0 indexed) of substrings of P which are matching with V according to the condition mentioned above. The indices have to be in an increasing order. If there is no matching output No Match!.
In a nutshell, it requires me to compare two strings and find the beginning index value for all occurrences of the second substring in the first. The catch is that upto one mismatch in the substring is allowed.
I've coded the following solution which seems to work well for the first 3 testcases. The problem is it timed-out after the 3rd test case. I can't seem to optimize it any further than what I've already done unless my logic is somehow overly complicated or I'm not using enough in-built methods to quicken things up.
inp = inp.split('\n')
del inp[0]
for h in inp:
P,sep,V = str(h).partition(' ')
upperlimit = len(P) - len(V) + 1
if P == V:
print("0")
continue
else:
matches=0
for i in range(0,upperlimit):
Psub = P[i:i+len(V)]
if Psub == V: # Check if they match exactly
print(str(i) + " ", end='')
matches += 1
continue # Just proceed with the next iteration of loop if they match
mismatches = 0
for j in range(0,len(V)): # If we hit this code then, we're about to see how many characters mismatch in the substring
if Psub[j] != V[j]:
mismatches += 1
if mismatches>=2: # No point checking the substrings alphabet by alphabet any further, more than 1 mismatch present here.
break
if mismatches<2:
print(str(i)+" ",end='')
matches += 1
if matches==0: # This is possible ONLY if none of the above conditions were ever met.
print("No Match!",end='')
print()
Can someone please tell me why code is slow? Also, let me know if you want me to comment more of my code so it's easier to understand. The link to the problem description should be quite useful in understanding the problem.
inp
in the first place? \$\endgroup\$