C++에서 예산 내에서 동일한 부분 문자열 가져오기

<시간/>

길이가 같은 두 개의 문자열과 t가 주어졌다고 가정합니다. 우리는 s를 t로 바꾸고 싶습니다. s의 i번째 문자를 t의 i번째 문자로 변경하면 비용이 |s[i] - t[i]|로 할당됩니다. 즉, 문자의 ASCII 값 간의 절대 차이입니다. 우리는 또한 정수 maxCost를 제공했습니다. maxCost보다 작거나 같은 비용으로 t의 해당 부분 문자열과 같도록 변경할 수 있는 s의 부분 문자열의 최대 길이를 찾아야 합니다.

따라서 입력이 s ="abcd" 및 t ="bcdf"와 같으면 maxCost는 3이 됩니다. 이는 s의 "abc"가 "bcd"로 변환될 수 있기 때문에 비용이 3이 되고 출력이 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

j :=0, 합계 :=0 및 ret :=0
범위 0에서 최소 s 및 t 크기의 i에 대해
- 합계를 |s[i] – t[i]|
  만큼 증가
- 합계> maxCost
  동안
  - 합계를 |s[i] – t[i]|
    만큼 감소
  - j를 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