<p>There is a strange printer with the following two special properties:</p>

<ul>
	<li>The printer can only print a sequence of <strong>the same character</strong> each time.</li>
	<li>At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.</li>
</ul>

<p>Given a string <code>s</code>, return <em>the minimum number of turns the printer needed to print it</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaabbb&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> Print &quot;aaa&quot; first and then print &quot;bbb&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aba&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> Print &quot;aaa&quot; first and then print &quot;b&quot; from the second place of the string, which will cover the existing character &#39;a&#39;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

struct CacheKey {
    std::string_view s;
    char c;
};

bool operator==(const CacheKey& l, const CacheKey& r) {
    return l.s == r.s && l.c == r.c;
}

struct CacheKeyHasher {
    size_t operator()(const CacheKey& k) const {
        return std::hash<std::string_view>()(k.s) ^ std::hash<char>()(k.c);
    }
};

using SubSolutionsCache =
    std::unordered_map<CacheKey, uint32_t, CacheKeyHasher>;

class Solution {
public:
    int strangePrinter(string s) {
        // Remove successive duplicates - they do not affect solution.
        s.erase(std::unique(s.begin(), s.end()), s.end());
        // std::cout << s << std::endl;

        SubSolutionsCache cache;
        auto res = SearchAdvanced_r(cache, s, ' ');
        std::cout << "Cache size: " << cache.size() << std::endl;
        return res;
    }

    uint32_t SearchAdvanced_r(SubSolutionsCache& cache,
                              const std::string_view s, const char filled_c) {
        {
            bool same = true;
            for (const char c : s)
                same &= c == filled_c;
            if (same)
                return 0;
        }

        if (const auto it = cache.find(CacheKey{s, filled_c});
            it != cache.end())
            return it->second;

        {
            uint32_t chars_set = 0u;
            bool has_duplicates = false;
            for (const char c : s) {
                const uint32_t mask = 1u << uint32_t((c - 'a'));
                if ((chars_set & mask) == 0u) {
                    chars_set |= mask;
                } else
                    has_duplicates = true;
            }
            if (!has_duplicates) {
                uint32_t res = s.size();
                if (filled_c != ' ' &&
                    (chars_set & (1u << uint32_t((filled_c - 'a')))) != 0u)
                    --res;
                // No need to fill cache for terminal strings.
                return res;
            }
        }

        uint8_t last_char_pos[26]{};
        for (size_t i = 0; i < s.size(); ++i)
            last_char_pos[s[i] - 'a'] = i;

        uint32_t min_steps = 999999;
        for (size_t i = 0; i < s.size(); ++i) {
            const char c = s[i];
            if (c == filled_c)
                continue;
            const size_t last_c_pos = last_char_pos[c - 'a'];

            uint32_t steps = 1u;

            if (last_c_pos - i > 1) {
                const std::string_view s_fill =
                    s.substr(i + 1, last_c_pos - i - 1);
                steps += SearchAdvanced_r(cache, s_fill, c);
                if (steps >= min_steps)
                    continue;
            }

            const std::string_view s_before_fill = s.substr(0, i);
            steps += SearchAdvanced_r(cache, s_before_fill, filled_c);
            if (steps >= min_steps)
                continue;

            const std::string_view s_after_fill = s.substr(last_c_pos + 1u);
            steps += SearchAdvanced_r(cache, s_after_fill, filled_c);
            if (steps >= min_steps)
                continue;

            min_steps = steps;
        }

        cache.emplace(CacheKey{s, filled_c}, min_steps);
        return min_steps;
    }
};

60652