LC-1208 Medium LeetCode

1208. Get Equal Substrings Within Budget

String Binary Search Sliding Window Prefix Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 59% Topics: String, Binary Search, Sliding Window, Prefix Sum

Reading material

Strings 12 min Binary Search 12 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def equalSubstring(self, s, t, maxCost):
        """
        :type s: str
        :type t: str
        :type maxCost: int
        :rtype: int
        """
        left = 0
        for right in xrange(len(s)):
            maxCost -= abs(ord(s[right])-ord(t[right]))
            if maxCost < 0:
                maxCost += abs(ord(s[left])-ord(t[left]))
                left += 1
        return (right+1)-left

Solution from kamyu104/LeetCode-Solutions · MIT