C++에서 K 회문 문자열 생성

<시간/>

문자열 s와 숫자 k가 있다고 가정합니다. s의 모든 문자를 사용하여 비어 있지 않은 k 개의 회문 문자열을 구성해야 합니다. 따라서 여기에서 s의 모든 문자를 사용하여 k 회문 문자열을 구성할 수 있는지 여부를 확인해야 합니다.

따라서 입력이 "true", k =4와 같으면 출력은 True가 됩니다. 가능한 유일한 해결책은 각 문자를 별도의 문자열에 넣는 것이기 때문입니다.

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

n :=s
의 크기
n
- 거짓 반환
n이 k와 같으면 -
- true를 반환
하나의 지도 정의
s
의 각 문자 c에 대해
- (m[c]를 1씩 증가)
홀수 :=0
각 키-값 쌍에 대해 m −
- 홀수 :=홀수 + (값 AND 1)
홀수 <=k이면 true를 반환하고, 그렇지 않으면 false
를 반환합니다.

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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

입력

"true"