Xây dựng K chuỗi Palindrome trong C ++

Giả sử chúng ta có một chuỗi s và một số k. Chúng ta phải tạo k chuỗi palindrome không rỗng bằng cách sử dụng tất cả các ký tự trong s. Vì vậy, ở đây chúng ta phải kiểm tra xem chúng ta có thể sử dụng tất cả các ký tự trong s để tạo k chuỗi palindrome hay không.

Vì vậy, nếu đầu vào là "true", k =4, thì đầu ra sẽ là True, vì giải pháp khả thi duy nhất là đặt mỗi ký tự trong một chuỗi riêng biệt.

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

• n:=kích thước của s

• nếu n

  • trả về false

• nếu n giống k thì -

  • trả về true

• Xác định một bản đồ

• cho mỗi ký tự c trong s

  • (tăng m [c] lên 1)

• lẻ:=0

• đối với mỗi khóa-giá trị, hãy ghép nối nó bằng m -

  • lẻ:=lẻ + (giá trị của nó VÀ 1)

• trả về true khi lẻ <=k, ngược lại là false

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canConstruct(string s, int k) {
      int n = s.size();
      if (n < k)
         return false;
      if (n == k)
         return true;
      map<char, int> m;
      for (char c : s)
         m[c]++;
      int odd = 0;
      for (auto& it : m) {
         odd += (it.second & 1);
      }
      return odd <= k;
   }
};
main(){
   Solution ob;
   cout << (ob.canConstruct("true",4));
}

Đầu vào

"true"

Đầu ra

1