LeetCode/cpp/maximum-length-of-a-concatenated-string-with-unique-characters.cpp

#include <bit>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

class Solution {
    static auto construct_sets(const std::vector<std::string> &arr)
        -> std::vector<uint32_t> {
        std::vector<std::uint32_t> sets;

        for (const auto &word : arr) {
            std::uint32_t w = 0;

            for (char c : word) {
                auto mask = 1 << (c - 'a');

                if ((w & mask) != 0) {
                    w = 0;
                    break;
                }
                w |= mask;
            }

            sets.push_back(w);
        }

        return sets;
    }

    static auto find_solution(const std::vector<std::uint32_t> &words,
                              std::size_t i, std::uint32_t w) -> int {
        if (i == words.size()) {
            return std::popcount(w);
        }

        auto found_solution = find_solution(words, i + 1, w);
        if ((words[i] & w) == 0) {
            found_solution = std::max(
                found_solution, find_solution(words, i + 1, w | words[i]));
        }

        return found_solution;
    }

  public:
    int maxLength(const std::vector<std::string> &arr) {
        auto sets = construct_sets(arr);
        return find_solution(sets, 0u, 0u);
    }
};

int main() {
    Solution s;

    assert(s.maxLength(std::vector{std::string{"un"}, std::string{"iq"},
                                   std::string{"ue"}}) == 4);
    assert(s.maxLength(std::vector{std::string{"cha"}, std::string{"r"},
                                   std::string{"act"}, std::string{"ers"}}) ==
           6);
    assert(s.maxLength(
               std::vector{std::string{"abcdefghijklmnopqrstuvwxyz"}}) == 26);

    return 0;
}