From d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 14 Jun 2024 13:13:15 -0600 Subject: initial --- get_equal_substr_budget.py | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 get_equal_substr_budget.py (limited to 'get_equal_substr_budget.py') diff --git a/get_equal_substr_budget.py b/get_equal_substr_budget.py new file mode 100644 index 0000000..5bca2a1 --- /dev/null +++ b/get_equal_substr_budget.py @@ -0,0 +1,35 @@ +# 1208. Get Equal Substrings Within Budget + +""" +you are given two strings 's' and 't' of the same length and an integer +'maxCost'. you want to change 's' to 't'. changing the i'th character of 's' +to the i'th character of 't' costs '|s[i] - t[i]|'. return the maximum length +of a substring of 's' that can be changed to be the same as the corresponding +substring of 't' with 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 +""" + + +class Solution(object): + def equalSubstring(self, s, t, maxCost): + """ + :type s: str + :type t: str + :type maxCost: int + :rtype: 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 + + +if __name__ == "__main__": + obj = Solution() + print(obj.equalSubstring(s="abcd", t="bcdf", maxCost=3)) + print(obj.equalSubstring(s="abcd", t="cdef", maxCost=3)) + print(obj.equalSubstring(s="abcd", t="acde", maxCost=0)) -- cgit v1.2.3