Most posts are wrong. (Or Am I wrong?)

  • 1

    I think most of the solutions posted here using 2-dimensional dp are wrong, but accidentally pass all the test cases:
    Most of the solutions are using:
    dp[i][j] : minimum print for the interval [i, j] or [i, j), and use that to do recursion. But I think this is incorrect: since it also depend on the printing of the previous time. For example, if the [i,j] has been printed by 'a' for the last time, then it is no longer the same as the initial state, since we do not need to print 'a' within this interval again.
    Here is my solution:
    I use a 3D array dp[i][j][k] do denote the minimum print need for the interval [j, k) if this interval was printed by char('a' + i -1) (i = 0 if this it has not being printed).
    Then during the recursion, not only we need to consider about indices t s.t. s[t] == s[j] but also need to consider t s.t. s[t] == char('a' + i -1).
    Am I wrong? (Maybe I am wrong.)
    Below is my solution:

    typedef vector<int> vi;
    class Solution {
        int dp [27][105][105], pos[27][105]; 
        string st;
        int n;
        int cnt(int ic,int i,int j){
            if(i>j) return 0;
            if(dp[ic][i][j] >= 0) return dp[ic][i][j];
            if(ic == (int)(st[i]-'a' + 1)) return dp[ic][i][j] = cnt(ic,i+1,j);
            if(ic == (int)(st[j]-'a' + 1)) return dp[ic][i][j] = cnt(ic,i,j-1);
            int kc = (int)(st[i]-'a' + 1), k = min(pos[kc][i],  pos[ic][i]);
            dp[ic][i][j] = n;
                k = min(j+1, k);
                dp[ic][i][j] = min(dp[ic][i][j], 1 + cnt(kc,i+1,k-1) + cnt(ic,k+1,j));
                if(k >= j) break;
                k = min(pos[kc][k],  pos[ic][k]);
            return dp[ic][i][j];
        int strangePrinter(string s) {
            if(s.empty()) return 0;
            st += s[0];
            for(int i=1;i<s.size();++i) if(s[i]!=s[i-1]) st+=s[i];
            n = st.size();
            map<char,int> mp;
            for(int i=0;i<27;++i) pos[i][n-1] = n;
            for(int j=n-2;j>=0;--j) for(int i=0;i<27;++i){
                if(i == (int)(st[j+1]- 'a' + 1)) pos[i][j] = j+1;
                else pos[i][j] = pos[i][j+1];
            return cnt(0,0,n-1);

  • 0

    Please provide a link to such a wrong solution and show an input where that solution returns a wrong result. (It's strange that you didn't do that right away.)

  • 0
    This post is deleted!

  • 0

    for the update dp[i][j] -> min(dp[i][k] + dp[k+1][j]) for all k where i<=k<=j && a[i] == a[k]:
    When the interval [i, k] be overwritten once by a[i], it is no longer the initial state (You do not need to print a[i] within this interval again, but for the initial state, you need.). Then the minimum prints need to cover this interval from this state is dp[i][k]|_{a[i]} which is not necessarily equal to dp[i][k] which is the minimum print of this interval from the very beginning when no character has been printed.
    I will try to construct a case when I get time.

  • 0

    I will try to construct a case when I get time.
    I am not 100% percent sure. I might be wrong.

  • 0

    You are wrong.
    Here is the proof

    I upvoted this post anyways, though, because I feel it was constructive and exposed an assumption in people's O(n^3) algorithms that needed to be examined rigorously.

Log in to reply

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