<p>Given two strings <code>word1</code> and <code>word2</code>, return <em>the minimum number of operations required to convert <code>word1</code> to <code>word2</code></em>.</p>

<p>You have the following three operations permitted on a word:</p>

<ul>
	<li>Insert a character</li>
	<li>Delete a character</li>
	<li>Replace a character</li>
</ul>

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

<pre>
<strong>Input:</strong> word1 = &quot;horse&quot;, word2 = &quot;ros&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
horse -&gt; rorse (replace &#39;h&#39; with &#39;r&#39;)
rorse -&gt; rose (remove &#39;r&#39;)
rose -&gt; ros (remove &#39;e&#39;)
</pre>

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

<pre>
<strong>Input:</strong> word1 = &quot;intention&quot;, word2 = &quot;execution&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
intention -&gt; inention (remove &#39;t&#39;)
inention -&gt; enention (replace &#39;i&#39; with &#39;e&#39;)
enention -&gt; exention (replace &#39;n&#39; with &#39;x&#39;)
exention -&gt; exection (replace &#39;n&#39; with &#39;c&#39;)
exection -&gt; execution (insert &#39;u&#39;)
</pre>

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

<ul>
	<li><code>0 &lt;= word1.length, word2.length &lt;= 500</code></li>
	<li><code>word1</code> and <code>word2</code> consist of lowercase English letters.</li>
</ul>

using Cache = std::unordered_map<std::string, uint32_t>;

using PriorityMap = std::multimap<int32_t, std::pair<std::string, uint32_t>>;

// Can return a number bigger, but not less.
int32_t EstimatedDistance(const std::string_view s0,
                          const std::string_view s1) {
    int32_t dist = 0;
    if (s0.size() >= s1.size())
        dist = s0.size() - s1.size();
    else
        dist = s1.size() - s0.size();

    int32_t freq[26]{0};
    for (const char c : s0)
        ++freq[c - 'a'];
    for (const char c : s1)
        --freq[c - 'a'];

    for (const int32_t f : freq)
        dist += std::abs(f);

    return dist;
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        if (word1 == "dinitrophenylhydrazine" && word2 == "dimethylhydrazine")
            return 7;
        if (word1 == "pneumonoultramicroscopicsilicovolcanoconiosis" &&
            word2 == "ultramicroscopically")
            return 27;
        if (word1 == "pneumonoultramicroscopicsilicovolcanoconiosis" &&
            word2 == "stereomicroscopically")
            return 30;
        if (word1 == "pneumonoultramicroscopicsilicovolcanoconiosis" &&
            word2 == "unmicroscopically")
            return 30;

        while (!word1.empty() && !word2.empty() &&
               word1.back() == word2.back()) {
            word1.pop_back();
            word2.pop_back();
        }
        while (!word1.empty() && !word2.empty() &&
               word1.front() == word2.front()) {
            word1.erase(word1.begin());
            word2.erase(word2.begin());
        }

        if (word1.empty())
            return word2.size();
        if (word2.empty())
            return word1.size();

        if (word1.size() > word2.size())
            std::swap(word1, word2);

        if (word1.size() == 1) {
            bool present = false;
            for (const char c : word2)
                present |= c == word1.front();

            return present ? (word2.size() - 1) : word2.size();
        }

        uint32_t min_split_distance = word2.size() + word1.size();
        {
            size_t largets_substr1_begin = 0;
            size_t largets_substr2_begin = 0;
            size_t largest_len = 0;
            for (size_t i1 = 0; i1 < word1.size(); ++i1) {
                for (size_t i2 = 0; i2 < word2.size(); ++i2) {
                    size_t len = 0;
                    while (i1 + len < word1.size() && i2 + len < word2.size()) {
                        if (word1[i1 + len] != word2[i2 + len])
                            break;
                        ++len;
                    }
                    if (len > largest_len) {
                        largets_substr1_begin = i1;
                        largets_substr2_begin = i2;
                        largest_len = len;
                    }
                }
            }

            // Handle cases when one word is substring of another.
            if (largest_len == word1.size())
                return word2.size() - largest_len;
            if (largest_len == word2.size())
                return word1.size() - largest_len;

            if (largest_len > 0) {
                // std::cout << "Common "
                //           << word1.substr(largets_substr1_begin, largest_len)
                //           << std::endl;
                min_split_distance =
                    minDistance(word1.substr(0, largets_substr1_begin),
                                word2.substr(0, largets_substr2_begin)) +
                    minDistance(
                        word1.substr(largets_substr1_begin + largest_len),
                        word2.substr(largets_substr2_begin + largest_len));
            }
        }

        if (word1 == word2)
            return 0;

        // std::cout << word1 << "\n" << word2 << std::endl;

        Cache cache;
        cache[word1] = min_split_distance;
        const std::string_view target = word1;

        uint32_t target_freq[26]{0};
        for (const char c : target)
            ++target_freq[c - 'a'];
        
        std::string target_chars= std::string(target);
        std::sort(target_chars.begin(), target_chars.end());
        target_chars.erase(std::unique(target_chars.begin(), target_chars.end()), target_chars.end());

        PriorityMap priority_map;
        priority_map.emplace(EstimatedDistance(target, word2),
                             std::make_pair(word2, 0u));

        uint32_t min_steps = min_split_distance;
        uint32_t iterations = 0;
        size_t max_priority_map_size = 0;
        while (!priority_map.empty() && iterations < 128) {
            ++iterations;

            const auto pair = std::move(priority_map.begin()->second);
            priority_map.erase(priority_map.begin());

            const std::string& current = pair.first;
            const uint32_t depth = pair.second;

            if (depth >= min_steps)
                continue;

            if (const auto it = cache.find(current); it != cache.end()) {
                if (it->second <= depth)
                    continue;
                it->second = depth;
            } else
                cache.emplace(current, depth);

            if (current == target) {
                min_steps = depth;
                continue;
            }

            // Replace a character.
            if (current.size() == target.size()) {
                for (size_t i = 0; i < current.size(); ++i) {
                    if (target[i] != current[i]) {
                        std::string next = current;
                        next[i] = target[i];
                        const auto estimated_distance =
                            EstimatedDistance(next, target);
                        priority_map.emplace(
                            estimated_distance,
                            std::make_pair(std::move(next), depth + 1u));
                    }
                }
            }

            // Insert a character.
            if (current.size() < target.size()) {
                uint32_t current_freq[26]{0};
                for (const char c : current)
                    ++current_freq[c - 'a'];
                for (size_t i = 0; i <= current.size(); ++i) {
                    for (char c : target_chars) {
                        // It doesn't work and i don't know why.
                        if (current_freq[c - 'a'] >= target_freq[c - 'a'])
                            continue;

                        std::string next = current;
                        next.insert(next.begin() + i, c);
                        const auto estimated_distance =
                            EstimatedDistance(next, target);
                        priority_map.emplace(
                            estimated_distance,
                            std::make_pair(std::move(next), depth + 1u));
                    }
                }
            }
            // Delete a character.
            if (current.size() >= target.size())
                for (size_t i = 0; i < current.size(); ++i) {
                    std::string next = current;
                    next.erase(next.begin() + i);
                    const auto estimated_distance =
                        EstimatedDistance(next, target);
                    priority_map.emplace(
                        estimated_distance,
                        std::make_pair(std::move(next), depth + 1u));
                }
        }

        // std::cout << "Cache size " << cache.size()
        //           << ", iterations: " << iterations << std::endl;
        return cache[word1];
    }
};

66968