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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Sorting

Amortized analysis

Range queries

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
		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:
		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
			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]
		for i in range(len(cost)):
			prefix.append(prefix[-1] + cost[i])
		maxLen = 0
		(i, j) = (0, 0)
		while j < len(cost):
			while j < len(cost) and prefix[j + 1] - prefix[i] <= maxCost:
				j += 1
			maxLen = max(maxLen, j - i)
			i += 1
			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


import numpy as np

class Solution:

	def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
		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


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


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
			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:
		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:
		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