Chuỗi tối thiểu trong C ++

Giả sử chúng ta có hai chuỗi s và t có cùng độ dài và cả hai đều ở dạng chữ thường. Hãy xem xét lúc đầu, chúng tôi đã sắp xếp lại các s thành bất kỳ thứ tự nào, sau đó đếm số lượng thay đổi tối thiểu cần thiết để biến các s thành t.

Vì vậy, nếu đầu vào là s =​​"eccynue", t ="science", thì đầu ra sẽ là 2 như thể chúng ta sắp xếp lại "eccynue" thành "yccence", sau đó thay thế y bằng s và c thứ hai với i, nó sẽ là "khoa học".

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

• ret:=0

• Xác định hai mảng cnt1 để giữ tần số của s và cnt2 để giữ tần số của t

• để khởi tạo i:=0, khi tôi <26, hãy cập nhật (tăng i lên 1), thực hiện -

  • ret:=ret + max (cnt1 [i] - cnt2 [i], 0)

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(string s, string t) {
      int ret = 0;
      vector <int> cnt1(26);
      vector <int> cnt2(26);
      for(int i = 0; i < s.size(); i++){
         cnt1[s[i] - 'a']++;
      }
      for(int i = 0; i < t.size(); i++){
         cnt2[t[i] - 'a']++;
      }
      for(int i = 0; i < 26; i++){
         ret += max(cnt1[i] - cnt2[i], 0);
      }
      return ret;
   }
};
int main(){
   Solution ob;
   cout << (ob.solve("eccynue", "science"));
}

Đầu vào

"eccynue", "science"

Đầu ra

2