You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.
You are also given an integer maxCost.
Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.
If there is no substring from s that can be changed to its corresponding substring from t, return 0.
 
Example 1:
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.
Example 2:
Input: s = "abcd", t = "cdef", maxCost = 3
Output: 1
Explanation: Each character in s costs 2 to change to charactor in t, so the maximum length is 1.

Example 3:
Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: You can't make any change, so the maximum length is 1.

 
Constraints:

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s and t only contain lower case English letters.

Difficulty: interview

Starter code:

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        

Solutions:
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        dist = [ abs( ord(s[i]) - ord(t[i]) )  for i in range(len(s))]
        
#         i = 0
#         cur = 0
#         res = 0
#         for j in range(len(s)):
#             cur += dist[j]
#             while cur>maxCost:
#                 cur -= dist[i]
#                 i += 1
#             res = max(res, j-i+1)
        
#         return res

        i = 0
        cost = maxCost
        for j in range(len(s)):
            cost -= dist[j]
            if cost < 0:
                cost += dist[i]
                i += 1
                
        return j-i+1
        
        


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        

        i=0
        ans=0
        
        curr = 0
        for j in range(0,len(s)):
            curr = curr + abs(ord(s[j])-ord(t[j]))
            if curr<=maxCost:
                ans = max(ans , j-i+1)
            else:
                curr = curr - abs(ord(s[i])-ord(t[i]))      
                i=i+1
               
            
            
        print()
        return ans

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        #I could first create an array with the cost of each character change

        currCost = 0
        maxLength = 0
        start = 0
        curr = 0
        costs = [abs(ord(s[i])- ord(t[i])) for i in range(len(s))]
        print(costs)
        while curr < len(costs):
            currCost += costs[curr]
            while currCost > maxCost:
                currCost = currCost - costs[start]
                start+=1
            if curr - start + 1 > maxLength:
                maxLength = curr - start + 1
            # print(f\"currCost: {currCost}, start: {start}, curr: {curr}\")
            curr +=1
        return maxLength


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        if not s: return 0
        costs = [abs(ord(si)-ord(ti)) for si, ti in zip(s, t)]
        ans = 0
        l, r = 0, 0
        cur_cost = 0
        print(costs)
        while l < len(s) and r < len(s):
            while r < len(s) and cur_cost <= maxCost:
                cur_cost += costs[r]
                r += 1
            ans = max(ans, r-l-1)
            
            while l < r and cur_cost > maxCost:
                cur_cost -= costs[l]
                l += 1
        ans = max(ans, r-l)
        return ans
        


class Solution:
    def equalSubstring(self, string: str, target: str, maxCost: int) -> int:
        cost = [0]*len(string)
        for i in range(len(string)) :
            if string[i] != target[i] : cost[i] += abs(ord(string[i]) - ord(target[i]))
            if i > 0 : cost[i]+= cost[i-1]
        answer = 0
        s=0
        for i in range(len(string)) :
            if cost[i] <= maxCost : answer = max(answer,i+1)
            else :
                while s<=i and cost[i]-cost[s]> maxCost: s+=1
                answer = max(answer,i-s)
                   
        return answer


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        cost = [abs(ord(s[i])-ord(t[i])) for i in range(len(s))]
        prefix = [0] # prefix[i] gives us cost[0] + ... + cost[i-1]
        for i in range(len(cost)):
            prefix.append(prefix[-1]+cost[i])
        maxLen = 0
        i,j = 0,0
        # print(prefix)
        while j < len(cost):
            while j < len(cost) and prefix[j+1]-prefix[i] <= maxCost:
                j += 1
            maxLen = max(maxLen,j-i)
            i += 1
            # j = i
            if i > j:
                j = i
        return maxLen

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        
        start = 0
        ans = 0
        cur = 0
        for end in range(len(s)):  
            val = abs(ord(s[end]) - ord(t[end]))
            cur += val
            if cur <= maxCost:
                ans = max(ans, end-start+1)
            else:
                while cur > maxCost:
                    cur -= abs(ord(s[start]) - ord(t[start]))
                    start += 1
                
        return ans

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
      
      res = 0
      c = [0]*(len(s)+1)
      j = 0
      for i in range(1, len(s)+1):
        c[i] += c[i-1]+abs(ord(s[i-1])-ord(t[i-1]))
        
        while c[i]>maxCost:
          c[i] -= abs(ord(s[j])-ord(t[j]))
          j += 1
        res = max(res, i-j)
      return res


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        max_length = 0
        start = 0
        end = 0
        cost = 0
        while end < len(s):
            c = abs(ord(s[end]) - ord(t[end]))
            if cost + c <= maxCost:
                cost += c
                end += 1
            else:
                cost -= abs(ord(s[start]) - ord(t[start]))
                start += 1
            max_length = max(max_length, end - start) 
        return max_length 


class Solution:
    def equalSubstring(self, s, t, maxCost):
        n = len(s)
        right = 0
        nowSum = 0
        res = 0
        for left in range(n):
            while right <= n - 1 and nowSum + abs(ord(s[right]) - ord(t[right])) <= maxCost: 
                nowSum += abs(ord(s[right]) - ord(t[right]))
                right += 1
            res = max(res, right - left)
            nowSum -= abs(ord(s[left]) - ord(t[left]))
        return res          

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        cost_array = [abs(a - b) for a, b in zip(map(ord, s), map(ord, t))]
        left = right = t = 0
        mx = 0
        while right < len(cost_array):
            t += cost_array[right]
            if t > maxCost:
                while left < len(cost_array) and t > maxCost:
                    t -= cost_array[left]
                    left += 1

            right += 1
            mx = max(mx, right - left)

        return mx

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        i = 0
        for j in range(len(s)):
            maxCost -= abs(ord(s[j]) - ord(t[j]))
            if maxCost < 0:
                maxCost += abs(ord(s[i]) - ord(t[i]))
                i += 1
        return j - i + 1


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        cost_array = [abs(a - b) for a, b in zip(list(map(ord, s)), list(map(ord, t)))]
        
        left = right = t = mx = 0
        
        while right < len(cost_array):
        
            t += cost_array[right]
            if t > maxCost:
                t -= cost_array[left]
                left += 1

            right += 1
            mx = max(mx, right - left)

        return mx



import numpy as np

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        #Ss = [ord(c) for c in s]
        #Tt = [ord(d) for d in t]
        #diff = np.abs(np.array(Ss)-np.array(Tt))
        #n = len(s)
        i = result = 0
        for j in range(len(s)):
            maxCost -= abs(ord(s[j])-ord(t[j]))
            while(maxCost<0):
                maxCost += abs(ord(s[i])-ord(t[i]))
                i+=1
            result = max(result,j-i+1)

        return result

import numpy as np

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        #table = np.zeros(len(s))
        i = result = 0
        for j in range(len(s)):
            maxCost -= abs(ord(s[j])-ord(t[j]))
            while(maxCost<0):
                maxCost += abs(ord(s[i])-ord(t[i]))
                i+=1
            result = max(result,j-i+1)
            #table[j] = j-i+1
        return result
        #return int(max(table))


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        res = curr = i = j = 0
        while i < len(s) and j < len(s):
            curr += abs(ord(s[j]) - ord(t[j]))
            j += 1
            while curr > maxCost:
                curr -= abs(ord(s[i]) - ord(t[i]))
                i += 1
            res = max(res, j - i)
        return res

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        currcost=0;i=0;j=0
        if(len(s)==0):
            return 0
        if(len(s)==1):
            if(abs(ord[s[0]])-ord(t[0])>=maxcost):
                return 1
            else:
                return 0
        currcost=0
        ans=0
        state=False
        while(i<len(s) and j<len(s)):
            if(currcost+abs(ord(s[j])-ord(t[j]))<=maxCost):
                currcost+=abs(ord(s[j])-ord(t[j]))
                j+=1
                state=True
            else:
                ans=max(ans,j-i)
                currcost-=abs(ord(s[i])-ord(t[i]))
                i+=1
                state=False
                if(i>=j):
                    j=i
                    currcost=0
        if state:
            ans=max(ans,j-i)
        return ans


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        max_substring = 0
        curr_substring = 0
        
        left = right = diff = 0
        
        while right < len(s):
            local_diff = abs(ord(s[right]) - ord(t[right]))
            if diff + local_diff <= maxCost:
                diff += local_diff
                right += 1
                curr_substring += 1
                max_substring = max(curr_substring, max_substring)
            else:
                if left == right:
                    right += 1
                else:
                    diff -= abs(ord(s[left]) - ord(t[left]))
                    curr_substring -= 1
                left += 1
        
        return max_substring


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        
        arr = [abs(ord(sc) - ord(tc)) for sc, tc in zip(s, t)]
        max_len = 0
        left, right = 0, 0
        curr_sum = 0
        max_len = 0
        while(right < len(arr)):
            curr_sum += arr[right]
            while(left < len(arr) and curr_sum > maxCost):
                curr_sum -= arr[left]
                left += 1
            max_len = max(max_len, right - left + 1)
            right += 1
        return max_len

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        start = 0
        cost = 0
        max_len = 0
        for end in range(len(s)):
            cost += abs(ord(s[end]) - ord(t[end]))
            while cost > maxCost:
                cost -= abs(ord(s[start]) - ord(t[start]))
                start += 1
            max_len = max(max_len,end - start + 1)
        return max_len
            
                


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        max_len = head = subtotal = 0
        for tail in range(len(s)):
            subtotal += abs(ord(s[tail]) - ord(t[tail]))
            while subtotal > maxCost:
                subtotal -= abs(ord(s[head]) - ord(t[head]))
                head += 1
            max_len = max(max_len, tail - head + 1)
        return max_len

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        totalCost = 0
        maxLength = 0
        
        costs = []
        left = 0
        length = 0
        for i in range(len(s)):
            costs.append(abs(ord(s[i]) - ord(t[i])))
            totalCost += costs[-1]
            length += 1
        
            if totalCost <= maxCost:
                maxLength = length if length > maxLength else maxLength
            else:
                while totalCost > maxCost:
                    totalCost -= costs[left]
                    left += 1
                    length -= 1
            
        return maxLength

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        cost = 0
        left = 0
        max_len = 0
        for right in range(n):
            cost += abs(ord(s[right]) - ord(t[right]))
            while cost > maxCost:
                cost -= abs(ord(s[left]) - ord(t[left]))
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len

import numpy as np

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        Ss = [ord(c) for c in s]
        Tt = [ord(d) for d in t]
        diff = np.abs(np.array(Ss)-np.array(Tt))
        n = len(diff)
        i = result = 0
        for j in range(n):
            maxCost -= diff[j]
            if maxCost<0:
                maxCost += diff[i]
                i+=1
            result = max(result,j-i+1)

        return result

class Solution:
    def equalSubstring(self, s, t, maxCost):
        cost = 0
        ans = 0
        left, right = 0, -1
        for s_c, t_c in zip(s, t):
            right += 1
            cost += abs(ord(s_c) - ord(t_c))
            while cost > maxCost:
                cost -= abs(ord(s[left]) - ord(t[left]))
                left += 1
            ans = max(ans, right - left + 1)
        return ans

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        end = 0
        result = 0

        allCost = 0
        for start in range(len(s)):
            if start >= 1:
                allCost -= abs(ord(s[start-1]) - ord(t[start-1]))

            while (end +1<len(s)+1) and (allCost+ abs(ord(s[end]) - ord(t[end]))<= maxCost):
                end += 1
                allCost += abs(ord(s[end-1]) - ord(t[end-1]))


            result = max(result, end-start)
        return result


import numpy as np

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        Ss = [ord(c) for c in s]
        Tt = [ord(d) for d in t]
        diff = np.abs(np.array(Ss)-np.array(Tt))
        n = len(diff)
        i = result = 0
        for j in range(n):
            maxCost -= diff[j]
            while(maxCost<0):
                maxCost += diff[i]
                i+=1
            result = max(result,j-i+1)

        return result

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        
        arr = []
        lim = len(s)
        for i in range(0,lim):
            arr.append(abs(ord(s[i])-ord(t[i])))
            
        sm = [arr[0]]
        
        for j in range(1,lim):
            sm.append(sm[-1]+arr[j])
        
        
        l = 0
        h = lim
        
        mx = 0
        while l<=h:
            m = (l+h)//2
            ###print(m)
            t = 0
            for i in range(0,lim-m):
                if sm[i+m]-sm[i]+arr[i]<=maxCost:
                    t = 1
                    break
            if t==1:
                if m+1>mx:mx = m+1
                l = m+1
            else:
                h = m-1
        return mx

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        start = 0
        end = 0
        cost = 0
        best = 0
        while end < len(s):
            while end < len(s) and cost + abs(ord(s[end]) - ord(t[end])) <= maxCost:
                cost += abs(ord(s[end]) - ord(t[end]))
                end += 1
            if start == end:
                start += 1
                end += 1
                continue
            best = max(best, end - start)
            cost -= abs(ord(s[start]) - ord(t[start]))
            start += 1
        return best

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        
        diff = []
        for i in range(len(s)):
            diff.append(abs(ord(s[i])-ord(t[i])))
        
        i=0
        ans=0
        
        curr = 0
        for j in range(0,len(s)):
            curr = curr + diff[j]
            if curr<=maxCost:
                ans = max(ans , j-i+1)
            else:
                curr = curr - diff[i]                
                i=i+1
        return ans

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        ans = 0
        cost = 0
        left,right=0,0
        while right < len(s):
            cost += abs(ord(s[right])-ord(t[right]))
            if cost > maxCost:
                cost -= abs(ord(s[left])-ord(t[left]))
                left += 1
            else:
                ans = max(ans,right-left+1)
            right += 1
        return ans
            


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        #I could first create an array with the cost of each character change

        currCost = 0
        maxLength = 0
        start = 0
        curr = 0
        while curr < len(s):
            currCost += abs(ord(s[curr])- ord(t[curr]))
            while currCost > maxCost:
                currCost = currCost - (abs(ord(s[start])- ord(t[start])))
                start+=1
            if curr - start + 1 > maxLength:
                maxLength = curr - start + 1
            curr +=1
        return maxLength


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        maxLength = 0
        currLength = 0
        currCost = 0
        
        for i in range(len(s)):
            currLength += 1
            currCost += abs(ord(s[i]) - ord(t[i]))
            while currCost > maxCost:
                currCost -= abs(ord(s[i-(currLength-1)]) - ord(t[i-(currLength-1)]))
                currLength -= 1
            maxLength = max(maxLength, currLength)
        
        return maxLength
    
# Time: O(n)
# Space: O(1)


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        res = 0
        i,j = 0,0
        while j < len(s):
            maxCost -= abs(ord(t[j]) - ord(s[j]))
            while maxCost < 0:
                maxCost += abs(ord(t[i]) - ord(s[i]))
                i += 1
            j += 1
            res = max(res, j -i)
        return res