Nhận các chuỗi con bằng nhau trong phạm vi ngân sách trong C ++

Giả sử chúng ta đã cho hai chuỗi s và t có cùng độ dài. Chúng tôi muốn đổi s thành t. Thay đổi ký tự thứ i của s thành ký tự thứ i của t sẽ gán giá thành là | s [i] - t [i] | nghĩa là, sự khác biệt tuyệt đối giữa các giá trị ASCII của các ký tự. Chúng tôi cũng đã đưa ra 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 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ì vậy, nếu đầu vào giống như s =“abcd” và t =“bcdf”, thì maxCost sẽ là 3, điều này là do “abc” trong s, có thể được chuyển đổi thành “bcd”, sẽ có giá 3, sau đó đầu ra sẽ là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• j:=0, sum:=0 và ret:=0

• cho tôi trong phạm vi từ 0 đến tối thiểu kích thước s và t

  • tăng tổng lên | s [i] - t [i] |

  • while sum> maxCost

    • giảm tổng của | s [i] - t [i] |

    • tăng j lên 1

  • ret:=max của ret và (i - j + 1)

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách 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

Đầu ra

3