1208. Get Equal Substrings Within Budget

Description:

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.

 

'''
[1] using list)

idea::
keep change cost at index from 0 to len(s or t) (ex. idx,cost= 0,3) in list
while maxCost>=0, find min cost in map and change...

code::
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        costs=[]
        
        for i in range(len(s)):
            costs.append(abs(ord(s[i])-ord(t[i])))
        
        
        max_length=0
        left=0
        cur_sum=0
        
        for right in range(len(costs)):             # two pointer
            cur_sum+=costs[right]
            
            if cur_sum <= maxCost:
                max_length=max(max_length,right-left+1)
            
            else:
                while left<=right and cur_sum>maxCost:
                    cur_sum-=costs[left]
                    left+=1
            
        return max_length

-T/C: O(n)  # n==len(s), three pass, one for storing change costs  and the others for finding max_length
-S/C: O(n)
'''

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