รับสตริงย่อยที่เท่ากันภายในงบประมาณใน C++

สมมติว่าเราได้ให้สองสตริง s และ t มีความยาวเท่ากัน เราต้องการเปลี่ยน s เป็น t การเปลี่ยนอักขระตัวที่ i ของ s เป็นอักขระตัวที่ i ของ t จะกำหนดต้นทุนเป็น |s[i] - t[i]| นั่นคือความแตกต่างโดยสิ้นเชิงระหว่างค่า ASCII ของอักขระ เรายังให้ maxCost จำนวนเต็ม เราต้องหาความยาวสูงสุดของสตริงย่อยของ s ที่สามารถเปลี่ยนแปลงได้เหมือนกับสตริงย่อยที่เกี่ยวข้องของ t โดยมีค่าใช้จ่ายน้อยกว่าหรือเท่ากับ maxCost

ดังนั้นหากอินพุตเป็นเหมือน s ="abcd" และ t ="bcdf" ดังนั้น maxCost จะเป็น 3 เนื่องจาก "abc" ใน s สามารถแปลงเป็น "bcd" ได้ ซึ่งจะมีค่าใช้จ่าย 3 จากนั้นผลลัพธ์ จะเป็น 3.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• j :=0, sum :=0 และ ret :=0

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดต่ำสุดของ s และ t

  • เพิ่มผลรวมโดย |s[i] – t[i]|

  • ในขณะที่ sum> maxCost

    • ลดผลรวมโดย |s[i] – t[i]|

    • เพิ่มขึ้น 1

  • ret :=สูงสุดของ ret และ (i – j + 1)

• รีเทิร์น

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −

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;
   }
};

อินพุต

"abcd"
"bcdf"
3

ผลลัพธ์

3