C++ 16 ms solution


  • 0
    V

    The run-time varies from 16 to 23 ms, using the smallest in the title :)

    This solution would work with just 2 cycles: "x" - beginning of the encoded string, and "i" - encoded string size. We can always assume the maximum number of repetitions, since the sliding "x" will find the best starting point, and re-processing of the partially encoded string will encode skipped parts (I am doing re-processing anyway for recursive cases like 3[2[abc]dd]).

    However, I am using the third cycle - "j" - that go through the number of repetitions. It improves the run-time (106 ms vs. 538 ms) as this seems to be more efficient than re-processing alone. However, I got better run-time by combining this third cycle and re-processing. I found experimentally that cycling through half of repetitions brings 106 ms down to 32 ms. Cycling down through 25% of repetitions gives this result - 16 ms.

    I believe that there is still some room for optimizations (e.g. avoid copying strings) and empirical improvements. This solution may not perform as good for some other input and may require additional tweaking.

    class Solution 
    {
    private:
        string encode_helper(string& s, bool top, unordered_map<string, string>& dp)
        {
            auto slen = s.size();
            if (slen < 5) return s; // minimal encoding size is 4 characters.
        
            if (dp.count(s) != 0) return dp[s];
        
            auto shortest = s;
        
            for (auto x = 0; x < slen - 4; ++x) // "x" is starting position to encode.
            {
                if (x + 4 > shortest.size())
                {
                    break; // cannot be shorter than that.
                }
    
                if (x > 0 && s[x - 1] <= '9') continue; // we cannot split in the middle of a number when zipping.
                    
                auto ss = s.substr(x);
                auto sslen = slen - x;
        
                for (auto i = 1; i <= sslen / 2; ++i) // "i" is substring size
                {
                    auto part = ss.substr(0, i);
        
                    if (part.size() + 3 > shortest.size())
                    {
                        break; // cannot be shorter than that.
                    }
        
                    auto maxreps = 1;
                    while (i * maxreps <= sslen && ss.substr(i * maxreps, i) == part)
                    {
                        ++maxreps;
                    }
                    
                    // Note. We do not need this cycle. It will work if we just check maxreps. The sliding x above will find the best
                    // place to encode the string, and running this procedure again on the encoded string (see below) will encode skipped parts.
                    // However, the performance is actually better if we add this cycle (106 ms vs. 538 ms), as re-running the entire
                    // function on the partially encoded string seems to be more expensive. I discovered, though, that mixing some cycling
                    // and some re-processing gives the best result. For example, if we cycle maxreps / 2 times, the run-time is 32 ms.
                    // And If we cycle maxreps / 4, the run-time becomes 19ms.
                    auto minreps = (maxreps < 3 ? 1 : (maxreps < 5 ? 2 : maxreps - maxreps / 4));
                    for (auto j = maxreps; j > minreps; --j) // "j" is the number of repetitions
                    {
                        if (j * part.size() < 5) break; // does not make sense to encode.
                        
                        auto remainder = s.substr(x + i * j);
                        auto prefix = s.substr(0, x) + to_string(j) + "[" + part + "]";
        
                        if (prefix.size() + (remainder.size() > 4 ? 4 : remainder.size()) > shortest.size())
                        {
                            break;
                        }
        
                        auto candidate = prefix + encode_helper(remainder, false, dp);
        
                        // trying to zip the string even more.
                        if (top)
                        {
                            auto candidate2 = encode_helper(candidate, false, dp);
                            while (candidate2 != candidate)
                            {
                                candidate = candidate2;
                                candidate2 = encode_helper(candidate, false, dp);
                            }
                        }
        
                        if (candidate.size() < shortest.size() || (candidate.size() == shortest.size() && candidate < shortest))
                        {
                            shortest = candidate;
                        }
                    }
                }
            }
        
            dp[s] = shortest;
            return shortest;
        }
            
    public:
        string encode(string s) 
        {
            unordered_map<string, string> dp;
            return encode_helper(s, true, dp);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.