My code get wrong answer at the last test.Could not figure the bug.shall someone help?


  • 0
    Y
    class Solution {
    public:
        string minWindow(string s, string t) {
            
            char ms[256]  = {0};
            char mt[256]  = {0};
            
            int n1 = s.size();
            int n2 = t.size(); // n2 is t's size;
            if(n2==0||n1==0) return "";
            
            int count = 0;
            int minWinSize = n1+1;
            int winFrom = 0;
            int winTo = n1;
            
            for(int i=0;i<n2;i++){
                mt[t[i]]++;
            }    
            
            for(int i=0,j=0;j<n1;j++){//  i is start ,j is end 
                if(mt[s[j]] == 0) continue;
                else{
                    ms[s[j]] ++;
                    if(ms[s[j]] <= mt[s[j]]){
                        count ++;
                    }     
                    if(count == n2){// find a window 
                        while(i<=j){// move start of window 
                            if(mt[s[i]]==0){ // no occurence in t continue
                                i++;
                                continue;
                            }else if(ms[s[i]] > mt[s[i]]){// more occurence appears continue
                                ms[s[i]]--;
                                i++;
                                continue;
                            }else{                        // situation when ms[s[i]] == mt[s[i]] ,threshold point check if window is smallest so                                                       // far and move start forward as well as go to next loop.
                                if(minWinSize > j-i+1){
                                    minWinSize = j-i+1;
                                    winFrom = i;
                                    winTo = j;
                                }
                                ms[s[i]]--;
                                i++;
                                count--;
                                break;
                            }
                        }
                    }
                }
            }
            if(minWinSize==n1+1){
                return "";
            }else{
                return s.substr(winFrom,winTo-winFrom+1);
            }
        }
    };

  • 0
    Y

    I found bug myself ....

        char ms[256]  = {0};
        char mt[256]  = {0};
    

    should be

        int ms[256]  = {0};
        int mt[256]  = {0};
    

    Then it passed ...

    Does someone know how the change will affect the output of the test...

    Thanks


  • 0
    T

    char's range is 0..65535, int is -2^31..2^31-1, if you get a T or S contianing 70k consecutive same letters, your array values overflow the 65k range.

    In your case it could be an underflow (below outputs 65535):

    char x = 0; // array or not doesn't matter, individual elements count
    x--;
    System.out.println((int)x); // (int) is there to prevent outputting the character
    

    Edit: whops, I just noticed it's C++ :)
    The same still stands, but (signed) char's range is even worse -128..127, so 200 same letters are enough to break your code.


Log in to reply
 

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