Lấy Các Chuỗi Con Bằng Nhau Trong Ngân Sách Trong C++

Giả sử chúng ta có hai chuỗi s và t cùng độ dài. Chúng ta muốn biến s thành t. Việc thay đổi ký tự thứ i của s thành ký tự thứ i của t sẽ tốn chi phí |s[i] - t[i]|, tức là hiệu tuyệt đối giữa các giá trị ASCII của các ký tự. Chúng ta cũng được cho một số nguyên maxCost. Chúng ta phải tìm độ dài tối đa của một chuỗi con của s có thể thay đổi để giống với chuỗi con tương ứng của t với chi phí nhỏ hơn hoặc bằng maxCost.

Ví dụ, nếu s = "abcd" và t = "bcdf", maxCost = 3, thì "abc" trong s có thể chuyển thành "bcd" với chi phí 3, kết quả là 3.

Để giải quyết, chúng ta làm theo các bước:

j := 0, sum := 0, ret := 0.
Với i từ 0 đến min(kích thước s, kích thước t):
- Tăng sum thêm |s[i] – t[i]|.
- Khi sum > maxCost:
  - Giảm sum đi |s[j] – t[j]|.
  - Tăng j lên 1.
- Cập nhật ret = max(ret, i - j + 1).
Trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int j = 0;
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < min((int)s.size(), (int)t.size()); i++){
            sum += abs(s[i] - t[i]);
            while(sum > maxCost){
                sum -= abs(s[j] - t[j]);
                j++;
            }
            ret = max(ret, i - j + 1);
        }
        return ret;
    }
};

Đầu vào

"abcd" "bcdf" 3

Lấy Các Chuỗi Con Bằng Nhau Trong Ngân Sách Trong C++

Ví dụ (C++)

Đầu vào

Đầu ra