Problem Explanation

Suppose you are given two strings, s and t. Our target is to transform string s into string t. We can do this by changing each character in s to the corresponding character in t. But each change isn't free. We need to pay the absolute difference between the ASCII values of the characters we want to swap.

Moreover, there is a limitation on the total cost that we are allowed to spend. We can't exceed the cost given by the integer maxCost.

What should we do to maximize the length of a substring from s that can be swapped into the corresponding substring from t without exceeding our budget?

Let's illustrate the problem with an example. For instance, s = "abcd", t = "bcdf", maxCost = 3. We can change "abc" of s into "bcd". That will cost us 3 which is exactly the same as our budget. So the maximum length is 3.

Solution Explanation

The solution for this problem employs the Sliding Window technique, which is a method of keeping track of a subset of elements in an array (or string, in this case) while iterating through it. The 'window' slides as the iteration progresses, allowing us to analyze a different portion of elements each time.

The idea here is to iterate through string s, keeping a moving window of characters. We widen our window by one character at a time, meantime decreasing our remaining budget by the cost of exchanging the new character in s to the corresponding character in t.

If at any point our budget becomes negative, and hence we've overstepped our limit, we readjust our window and balance our budget by eliminating the cost of changing the first character of our current window substring in s into the corresponding character in t.

This way we're keeping track of the longest substring that we can afford to convert from string s to string t.

Python Solution

In Python, we can use the ord() function to turn a character into its corresponding ASCII value.

1
2python
3class Solution:
4    def equalSubstring(self, s: str, t: str, max_cost: int) -> int:
5        left = 0
6        for right in range(len(s)):
7            max_cost -= abs(ord(s[right]) - ord(t[right]))
8            if max_cost < 0:
9                max_cost += abs(ord(s[left]) - ord(t[left])) # adjust window
10                left += 1
11        return len(s) - left

Java Solution

In Java, we can cast a char to int to get its ASCII value.

1
2java
3class Solution {
4    public int equalSubstring(String s, String t, int maxCost) {
5        int j = 0;
6        for (int i = 0; i < s.length(); ++i) {
7            maxCost -= Math.abs(s.charAt(i) - t.charAt(i));
8            if (maxCost < 0)
9                maxCost += Math.abs(s.charAt(j) - t.charAt(j++)); // adjust window
10        }
11        return s.length() - j;
12    }
13};

JavaScript Solution

For JavaScript, we can use the charCodeAt() method on a string to get the ASCII value of a character at a given index.

1
2javascript
3class Solution {
4    equalSubstring(s, t, maxCost) {
5        let j = 0;
6        for (let i = 0; i < s.length; i++) {
7            maxCost -= Math.abs(s.charCodeAt(i) - t.charCodeAt(i));
8            if (maxCost < 0) {
9                maxCost += Math.abs(s.charCodeAt(j) - t.charCodeAt(j++)); // adjust window
10            }
11        }
12        return s.length - j;
13    }
14}

C++ Solution

In C++, a char can be automatically promoted to int to perform arithmetic operations, which in this case gives us its ASCII value.

1
2cpp
3class Solution {
4public:
5    int equalSubstring(string s, string t, int maxCost) {
6        int j = 0;
7        for (int i = 0; i < s.size(); ++i) {
8            maxCost -= abs(s[i] - t[i]);
9            if (maxCost < 0)
10                maxCost += abs(s[j] - t[j++]); // adjust window
11        }
12        return s.size() - j;
13    }
14};

C# Solution

In C#, we can cast a char to int to get its ASCII value.

1
2csharp
3public class Solution {
4    public int EqualSubstring(string s, string t, int maxCost) {
5        int j = 0;
6        for (int i = 0; i < s.Length; ++i) {
7            maxCost -= Math.Abs(s[i] - t[i]);
8            if (maxCost < 0)
9                maxCost += Math.Abs(s[j] - t[j++]); // adjust window
10        }
11        return s.Length - j;
12    }
13}

Rust Solution

In Rust, we can get the ASCII value of a character by using the as keyword.

1
2rust
3impl Solution {
4    pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
5        let s = s.bytes().collect::<Vec<u8>>();
6        let t = t.bytes().collect::<Vec<u8>>();
7        let mut max_cost = max_cost;
8        let (mut j, mut i) = (0, 0);
9        while i != s.len() {
10            max_cost -= (s[i] as i32 - t[i] as i32).abs();
11            if max_cost < 0 {
12                max_cost += (s[j] as i32 - t[j] as i32).abs();
13                j += 1;
14            }
15            i += 1;
16        }
17        i as i32 - j as i32
18    }
19}

Swift Solution

In Swift, the asciiValue property returns the ASCII value of a character as an UInt8.

1
2swift
3class Solution {
4    func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
5        let s = Array(s), t = Array(t)
6        var left = 0, maxCost = maxCost
7        for right in 0..<s.count {
8            if let asciiS = s[right].asciiValue, let asciiT = t[right].asciiValue {
9                maxCost -= abs(Int(asciiS) - Int(asciiT))
10            }
11            if maxCost < 0 {
12                if let asciiS = s[left].asciiValue, let asciiT = t[left].asciiValue {
13                    maxCost += abs(Int(asciiS) - Int(asciiT)) // adjust window
14                }
15                left += 1
16            }
17        }
18        return s.count - left
19    }
20}

Go Solution

In Go, characters are by default numeric, so we can directly subtract two characters to get the difference.

1
2go
3func equalSubstring(s string, t string, maxCost int) int {
4    j := 0
5    for i := range s {
6        maxCost -= abs(int(s[i]) - int(t[i]))
7        if maxCost < 0 {
8            maxCost += abs(int(s[j]) - int(t[j]))
9            j++
10        }
11    }
12    return len(s) - j
13}
14
15func abs(n int) int {
16    if n < 0 {
17        return -n
18    }
19    return n
20}

Each of the above implementations closely follows the sliding window strategy described in the initial solution. The window extends if the cost is within the budget and shrinks when the budget is exhausted, and the maximum length of the string that can be transformed within the budget is returned.