หา Substring ยาวที่สุดที่แก้ไขได้ภายใน Budget (Get Equal Substrings Within Budget) ใน C++

ให้ String สองตัว s และ t ความยาวเท่ากัน เราต้องการเปลี่ยน s ให้กลายเป็น t โดยการเปลี่ยนตัวอักษรตำแหน่งที่ i จาก s[i] เป็น t[i] มี **ค่าใช้จ่าย (Cost)** เท่ากับ |s[i] - t[i]| (ค่าสัมบูรณ์ของความต่าง ASCII)

กำหนด maxCost เป็นงบประมาณสูงสุด หา **ความยาวสูงสุด (Maximum Length)** ของ Substring ที่สามารถเปลี่ยนได้ภายในงบประมาณนี้

ตัวอย่าง

s = "abcd", t = "bcdf", maxCost = 3

• Substring "abc" ใน s -> "bcd" ใน t
• Cost = |'a'-'b'| + |'b'-'c'| + |'c'-'d'| = 1+1+1 = 3
• คำตอบ = 3

อัลกอริทึม: Sliding Window (Two Pointers)

1. ใช้ 2 Pointer: j (Left), i (Right) ขยาย Window ไปทางขวา
2. เก็บ sum = ค่าใช้จ่ายสะสมใน Window ปัจจุบัน
3. ถ้า sum > maxCost -> หด Window ด้านซ้าย (j++) จนกว่า sum <= maxCost
4. อัปเดตคำตอบ ret = max(ret, i - j + 1) ทุกขั้นตอน

ตัวอย่างโค้ด C++

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int j = 0;          // Left pointer
        int sum = 0;        // Current cost
        int ret = 0;        // Max length found

        for (int i = 0; i < min(s.size(), t.size()); i++) {
            sum += abs(s[i] - t[i]);   // Expand right

            // Shrink left while over budget
            while (sum > maxCost) {
                sum -= abs(s[j] - t[j]);
                j++;
            }

            ret = max(ret, i - j + 1); // Update answer
        }
        return ret;
    }
};

Input / Output

Input:  "abcd" "bcdf" 3
Output: 3

ความซับซ้อน (Complexity)

• Time: O(N) — แต่ละตัวอักษรถูกเพิ่ม/ลบจาก Window สูงสุด 1 ครั้ง
• Space: O(1) — ใช้ตัวแปรคงที่

เทคนิค Sliding Window เหมาะสำหรับโจทย์หา Subarray/Substring ที่สatisfy เงื่อนไขแบบ "ผลรวมไม่เกิน K" ครับ