While your algorithm is \$O(n)\$, the constant factors are considerable. Specifically, you are suffering due to all the nodes the map needs.

Better options are:

1. Just std::sort() and then do a single pass. While the order is \$O(n * log(n))\$, it will probably still be far more efficient.

2. Use an array for a histogram. 256 elements (wrap-around of an unsigned type would be safe, so unsigned char suffices) should fit comfortably.
   Even if you are on a rare platform with bigger bytes, it ought to fit or you have bigger problems with your current implementation.
   While the order is the same, the constants are far smaller.

Regarding your implementation:

1. Unless you need a null-terminated read-only string, passing by std::string const& is very sub-optimal. Considering your chosen algorithm, std::string_view would be best.

2. You could mark your algorithm constexpr.
   noexcept unfortunately eludes you due to all the allocations.

constexpr bool is_permutation_palindrome(std::string_view s) noexcept {
    unsigned char counts[1u + (unsigned char)-1] {};
    for (unsigned char c : s)
        ++counts[c];
    return std::ranges::count_if(counts, [](auto a){ return a % s; }) < 2;
}

While your algorithm is \$O(n)\$, the constant factors are considerable. Specifically, you are suffering due to all the nodes the map needs.

Better options are:

1. Just std::sort() and then do a single pass. While the order is \$O(n * log(n))\$, it will probably still be far more efficient.

2. Use an array for a histogram. 256 elements (wrap-around of an unsigned type would be safe, so unsigned char suffices, or even flipping a bool) should fit comfortably.
   Even if you are on a rare platform with bigger bytes, it ought to fit or you have bigger problems with your current implementation.
   While the order is the same, the constants are far smaller.

Regarding your implementation:

1. Unless you need a null-terminated read-only string, passing by std::string const& is very sub-optimal. Considering your chosen algorithm, std::string_view would be best.

2. You could mark your algorithm constexpr.
   noexcept unfortunately eludes you due to all the allocations.

constexpr bool is_permutation_palindrome(std::string_view s) noexcept {
    unsigned char counts[1u + (unsigned char)-1] {};
    for (unsigned char c : s)
        ++counts[c];
    return std::ranges::count_if(counts, [](auto a){ return a % 2; }) < 2;
}

While your algorithm is \$O(n * log(n))\$, the constant factors are considerable. Specifically, you are suffering due to all the nodes the map needs.

Better options are:

1. Just std::sort() and then do a single pass. While the order is the same, it will be far more efficient.

2. Use an array for a histogram. 256 elements (wrap-around of an unsigned type would be safe, so unsigned char suffices) should fit comfortably.
   Even if you are on a rare platform with bigger bytes, it ought to fit or you have bigger problems with your current implementation.

Regarding your implementation:

1. Unless you need a null-terminated read-only string, passing by std::string const& is very sub-optimal. Considering your chosen algorithm, std::string_view would be best.

2. You could mark your algorithm constexpr.
   noexcept unfortunately eludes you due to all the allocations.

constexpr bool is_permutation_palindrome(std::string_view s) noexcept {
    unsigned char counts[1u + (unsigned char)-1] {};
    for (unsigned char c : s)
        ++counts[c];
    return std::ranges::count_if(counts, [](auto a){ return a % s; }) < 2;
}

While your algorithm is \$O(n)\$, the constant factors are considerable. Specifically, you are suffering due to all the nodes the map needs.

Better options are:

1. Just std::sort() and then do a single pass. While the order is \$O(n * log(n))\$, it will probably still be far more efficient.

2. Use an array for a histogram. 256 elements (wrap-around of an unsigned type would be safe, so unsigned char suffices) should fit comfortably.
   Even if you are on a rare platform with bigger bytes, it ought to fit or you have bigger problems with your current implementation.
   While the order is the same, the constants are far smaller.

Regarding your implementation:

1. Unless you need a null-terminated read-only string, passing by std::string const& is very sub-optimal. Considering your chosen algorithm, std::string_view would be best.

2. You could mark your algorithm constexpr.
   noexcept unfortunately eludes you due to all the allocations.

constexpr bool is_permutation_palindrome(std::string_view s) noexcept {
    unsigned char counts[1u + (unsigned char)-1] {};
    for (unsigned char c : s)
        ++counts[c];
    return std::ranges::count_if(counts, [](auto a){ return a % s; }) < 2;
}