Get Wrong with the large test case. Can anyone me where I am wrong


  • 0
    Y
    public class Solution {
    public static String minWindow(String S, String T) 
    {
        if(T.length()==0||S.length()==0||S.length()<T.length())
        {
            String solution = "";
            return solution;
        }
        HashMap<Character,Integer> omap = new HashMap<Character,Integer>();
        HashSet<Character> cset = new HashSet<Character>();
        for(int i=0;i<T.length();i++)
        {
            if(omap.containsKey(T.charAt(i)))
            {
                omap.put(T.charAt(i),omap.get(T.charAt(i))+1);
            }
            else
            {
                omap.put(T.charAt(i),1);
            }
            cset.add(T.charAt(i));
        }
       Queue<Integer> q = new LinkedList<Integer>();
       HashMap<Character,Integer> map = new HashMap<Character,Integer>();
       int begin= -1;
       int end = S.length();
       int b=-1;
       int e = S.length();
       for(int i=0;i<S.length();i++)
       {
           char ch = S.charAt(i);
           if(cset.contains(ch))
           {
               if(map.containsKey(ch))
               {
                   map.put(ch,map.get(ch)+1);
               }
               else
               {
                   map.put(ch,1);
               }
               if(map.get(ch)==omap.get(ch))
               {
                   cset.remove(ch);
               }
               q.offer(i);
               if(cset.isEmpty())
               {
            	   
                   e = i;
                   while(map.get(S.charAt(q.peek()))>omap.get(S.charAt(q.peek())))
                   {
                       map.put(S.charAt(q.peek()),map.get(S.charAt(q.peek()))-1);
                       q.poll();
                   }
                   b = q.peek();
                   if(e-b<end-begin)
                   {
                       end = e;
                       begin = b;
                   }
                   int index = q.poll();
                   if(map.get(S.charAt(index))<=1)
                   {
                       map.remove(S.charAt(index));
                   }
                   else
                   {
                       map.put(S.charAt(index),map.get(S.charAt(index))-1);
                   }
                   cset.add(S.charAt(index));
               }
               
           }
           else
           {
               
               if(map.containsKey(ch))
               {
                    map.put(ch,map.get(ch)+1);
                    q.offer(i);
               }
               
           }
       }
       if(begin>-1&&end<S.length())
       {
           return S.substring(begin,end+1);
       }
       else
       {
           String solution = "";
           return solution;
       }
       
        
    }
    

    }

    It output "" for the largest case "kgfidhktkjhlkbgjkylgdracfzjduycghkomrbfbkoowqwgaurizliesjnveoxmvj..."


  • 0
    Y

    I make it right by changing

    if(map.get(ch)==omap.get(ch))
    {
                   cset.remove(ch);
    }
    

    to

    if(map.get(ch)>=omap.get(ch))
    {
                   cset.remove(ch);
    }
    

    But a very interesting thing is if I change it to

    if(map.get(ch)>omap.get(ch))
    {
                   cset.remove(ch);
    }
    else if(map.get(ch)==omap.get(ch))
    {
                   cset.remove(ch);
    }
    

    It becomes wrong again, but it is not "", but another string.


  • 0
    Y

    map.get(ch) is an Integer, and omap.get(ch) is also an Integer. The == for two objects does not compare the value they contain. it checks whether the two objects are same. You could try:
    map.get(ch).intValue() == omap.get(ch).intValue()
    Hope it helps


  • 0
    B

    Hey yzhao,

    Your replay is wrong.

    Integer i = 1;
    Integer j = 1;
    System.out.println((i == j) + "!");

    it prints "true!". I think Integer overrides == operand


  • 0
    C

    Hey bulinyangzi, yzhao's reply is right. Try the following:


    Integer i = new Integer(1);
    Integer j = new Integer(1);
    System.out.println(i==j);


    The output will be false.
    Your's example is true, because the objects reference i and j have been assigned to the same object.


  • 0
    L

    try this: replace "map.get(ch)==omap.get(ch)" with "map.get(ch)+0==omap.get(ch)". your solution will be accepted.


Log in to reply
 

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