Interview Question
SDE-2sCountry: India
Interview Type: Written Test
def lss(special_bits, s, k):
dp = [[(0,-1)]*(len(s)+1)] + [[(0,0)]*(len(s)+1) for i in range(k+1)]
res = 0
for i,x in enumerate(s):
is_normal = special_bits[ord(x)-ord('a')] == '0'
is_special = 1-is_normal
for j in range(k+1):
normal_count, max_len = dp[j+is_special][i]
dp[j+1][i+1] = (normal_count+is_normal, max_len+1)
res = max(res, max_len+1)
return res
print (lss('01111001111111111011111111', 'giraffe', 1))
I am confused by your example. The bit mask '011110011111111110111111' is 2 characters short. Presuming you meant '01111001111111111011111111' which you mentioned the first time, the normal characters would be ['a', 'f', 'g', 'r'], however you say that 'gir' has only one normal character which does not make sense.
- adr September 22, 2019