1208. Get Equal Substrings Within Budget

Description

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 i^th character of t costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of the characters).

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.

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 character in t,  so the maximum length is 1.

Example 3:

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

Constraints:

1 <= s.length <= 10⁵
t.length == s.length
0 <= maxCost <= 10⁶
s and t consist of only lowercase English letters.

Solutions

Solution 1: Prefix Sum + Binary Search

We can create an array $f <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>f</mi></math>$ of length $n + 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mo>+</mo><mn>1</mn></math>$ , where $f [i] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>f</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo></math>$ represents the sum of the absolute differences of ASCII values between the first $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ characters of string $s <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi></math>$ and the first $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ characters of string $t <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>t</mi></math>$ . Thus, we can calculate the sum of the absolute differences of ASCII values from the $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ -th character to the $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ -th character of string $s <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi></math>$ by $f [j + 1] - f [i] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>f</mi><mo stretchy="false">[</mo><mi>j</mi><mo>+</mo><mn>1</mn><mo stretchy="false">]</mo><mo>-</mo><mi>f</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo></math>$ , where $0 \leq i \leq j < n <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn><mo>\leq</mo><mi>i</mi><mo>\leq</mo><mi>j</mi><mo><</mo><mi>n</mi></math>$ .

Note that the length has monotonicity, i.e., if there exists a substring of length $x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$ that satisfies the condition, then a substring of length $x - 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi><mo>-</mo><mn>1</mn></math>$ must also satisfy the condition. Therefore, we can use binary search to find the maximum length.

We define a function $c h e c k (x) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>c</mi><mi>h</mi><mi>e</mi><mi>c</mi><mi>k</mi><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo></math>$ , which indicates whether there exists a substring of length $x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$ that satisfies the condition. In this function, we only need to enumerate all substrings of length $x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$ and check whether they satisfy the condition. If there exists a substring that satisfies the condition, the function returns true, otherwise it returns false.

Next, we define the left boundary $l <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>l</mi></math>$ of binary search as $0 <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math>$ and the right boundary $r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>r</mi></math>$ as $n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$ . In each step, we let $mid=⌊l+r+12⌋<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>m</mi><mi>i</mi><mi>d</mi><mo>=</mo><mo fence="false" stretchy="false">⌊</mo><mfrac><mrow><mi>l</mi><mo>+</mo><mi>r</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo fence="false" stretchy="false">⌋</mo></math>$ . If the return value of $c h e c k (m i d) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>c</mi><mi>h</mi><mi>e</mi><mi>c</mi><mi>k</mi><mo stretchy="false">(</mo><mi>m</mi><mi>i</mi><mi>d</mi><mo stretchy="false">)</mo></math>$ is true, we update the left boundary to $m i d <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>m</mi><mi>i</mi><mi>d</mi></math>$ , otherwise we update the right boundary to $m i d - 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>m</mi><mi>i</mi><mi>d</mi><mo>-</mo><mn>1</mn></math>$ . After the binary search, the left boundary we get is the answer.

The time complexity is $O (n \times log n) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>\times</mo><mi>log</mi><mo data-mjx-texclass="NONE"></mo><mi>n</mi><mo stretchy="false">)</mo></math>$ , and the space complexity is $O (n) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></math>$ . Here, $n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$ is the length of string $s <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi></math>$ .

Solution 2: Two Pointers

We can maintain two pointers

j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>

and

i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>

, initially

i = j = 0 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi><mo>=</mo><mi>j</mi><mo>=</mo><mn>0</mn></math>

; maintain a variable

s u m <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi><mi>u</mi><mi>m</mi></math>

, representing the sum of the absolute differences of ASCII values in the index interval

[i, . . j] <math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">[</mo><mi>i</mi><mo>,</mo><mo>.</mo><mo>.</mo><mi>j</mi><mo stretchy="false">]</mo></math>

. In each step, we move

i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>

to the right by one position, then update $sum = sum +

s[i] - t[i]

. I f <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>.</mo><mi>I</mi><mi>f</mi></math>

sum \gt maxCost

, t h e n w e m o v e t h e p o i n t e r <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>,</mo><mi>t</mi><mi>h</mi><mi>e</mi><mi>n</mi><mi>w</mi><mi>e</mi><mi>m</mi><mi>o</mi><mi>v</mi><mi>e</mi><mi>t</mi><mi>h</mi><mi>e</mi><mi>p</mi><mi>o</mi><mi>i</mi><mi>n</mi><mi>t</mi><mi>e</mi><mi>r</mi></math>

t o t h e r i g h t i n a l o o p, a n d c o n t i n u o u s l y r e d u c e t h e v a l u e o f <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>t</mi><mi>o</mi><mi>t</mi><mi>h</mi><mi>e</mi><mi>r</mi><mi>i</mi><mi>g</mi><mi>h</mi><mi>t</mi><mi>i</mi><mi>n</mi><mi>a</mi><mi>l</mi><mi>o</mi><mi>o</mi><mi>p</mi><mo>,</mo><mi>a</mi><mi>n</mi><mi>d</mi><mi>c</mi><mi>o</mi><mi>n</mi><mi>t</mi><mi>i</mi><mi>n</mi><mi>u</mi><mi>o</mi><mi>u</mi><mi>s</mi><mi>l</mi><mi>y</mi><mi>r</mi><mi>e</mi><mi>d</mi><mi>u</mi><mi>c</mi><mi>e</mi><mi>t</mi><mi>h</mi><mi>e</mi><mi>v</mi><mi>a</mi><mi>l</mi><mi>u</mi><mi>e</mi><mi>o</mi><mi>f</mi></math>

sum

d u r i n g t h e m o v i n g p r o c e s s u n t i l <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi><mi>u</mi><mi>r</mi><mi>i</mi><mi>n</mi><mi>g</mi><mi>t</mi><mi>h</mi><mi>e</mi><mi>m</mi><mi>o</mi><mi>v</mi><mi>i</mi><mi>n</mi><mi>g</mi><mi>p</mi><mi>r</mi><mi>o</mi><mi>c</mi><mi>e</mi><mi>s</mi><mi>s</mi><mi>u</mi><mi>n</mi><mi>t</mi><mi>i</mi><mi>l</mi></math>

sum \leq maxCost

. T h e n w e u p d a t e t h e a n s w e r, i . e ., <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>.</mo><mi>T</mi><mi>h</mi><mi>e</mi><mi>n</mi><mi>w</mi><mi>e</mi><mi>u</mi><mi>p</mi><mi>d</mi><mi>a</mi><mi>t</mi><mi>e</mi><mi>t</mi><mi>h</mi><mi>e</mi><mi>a</mi><mi>n</mi><mi>s</mi><mi>w</mi><mi>e</mi><mi>r</mi><mo>,</mo><mi>i</mi><mo>.</mo><mi>e</mi><mo>.</mo><mo>,</mo></math>

ans = \max(ans, i - j + 1)$.

Finally, return the answer.

The time complexity is $O (n) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></math>$ , and the space complexity is $O (1) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></math>$ . Here, $n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$ is the length of string $s <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi></math>$ .

class Solution {
    private int maxCost;
    private int[] f;
    private int n;

    public int equalSubstring(String s, String t, int maxCost) {
        n = s.length();
        f = new int[n + 1];
        this.maxCost = maxCost;
        for (int i = 0; i < n; ++i) {
            int x = Math.abs(s.charAt(i) - t.charAt(i));
            f[i + 1] = f[i] + x;
        }
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >>> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private boolean check(int x) {
        for (int i = 0; i + x - 1 < n; ++i) {
            int j = i + x - 1;
            if (f[j + 1] - f[i] <= maxCost) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.size();
        int f[n + 1];
        f[0] = 0;
        for (int i = 0; i < n; ++i) {
            f[i + 1] = f[i] + abs(s[i] - t[i]);
        }
        auto check = [&](int x) -> bool {
            for (int i = 0; i + x - 1 < n; ++i) {
                int j = i + x - 1;
                if (f[j + 1] - f[i] <= maxCost) {
                    return true;
                }
            }
            return false;
        };
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        def check(x):
            for i in range(n):
                j = i + mid - 1
                if j < n and f[j + 1] - f[i] <= maxCost:
                    return True
            return False

        n = len(s)
        f = list(accumulate((abs(ord(a) - ord(b)) for a, b in zip(s, t)), initial=0))
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

func equalSubstring(s string, t string, maxCost int) int {
	n := len(s)
	f := make([]int, n+1)
	for i, a := range s {
		f[i+1] = f[i] + abs(int(a)-int(t[i]))
	}
	check := func(x int) bool {
		for i := 0; i+x-1 < n; i++ {
			if f[i+x]-f[i] <= maxCost {
				return true
			}
		}
		return false
	}
	l, r := 0, n
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

function equalSubstring(s: string, t: string, maxCost: number): number {
    const n = s.length;
    const f = Array(n + 1).fill(0);

    for (let i = 0; i < n; i++) {
        f[i + 1] = f[i] + Math.abs(s.charCodeAt(i) - t.charCodeAt(i));
    }

    const check = (x: number): boolean => {
        for (let i = 0; i + x - 1 < n; i++) {
            if (f[i + x] - f[i] <= maxCost) {
                return true;
            }
        }
        return false;
    };

    let l = 0,
        r = n;
    while (l < r) {
        const mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    return l;
}

1208 - Get Equal Substrings Within Budget

1208. Get Equal Substrings Within Budget

Description

Solutions

All Problems

All Solutions

Welcome to Subscribe On Youtube

1208. Get Equal Substrings Within Budget

Description

Solutions

All Problems

All Solutions