Demo entry 6346651

ds

   

Submitted by anonymous on Feb 11, 2017 at 08:14
Language: Java. Code size: 2.4 kB.

    
    public List<Integer> findt2string(String t1, String t2) 
    {
        List<Integer> res = new LinkedList<>();
        if (t2.length() == 0 || t1.length() == 0 || t1.length() < t2.length())   
        {
            return res;
        }
        int t1Len = t1.length(), t2Len = t2.length;
        Map<String, Integer> t2Map = new HashMap<>(), curMap = new HashMap<>();
        int total = 0;
        for (char c : t2.toCharArray()) 
        {
            if (t2Map.containsKey(c))   
            {
           
                t2Map.put(c, t2Map.get(c) + 1);
            }
            else                      
            {
                t2Map.put(c, 1);
            }
            total++;
        }
        int count = 0;  // remark: reset count 
        for (int l = 0, r = 0; r + t2Len <= t1Len; r++) 
        {
            if (t2Map.containsKey(t1[r])) 
                {
                    if (curMap.containsKey(t1[r]))   
                    {
                        curMap.put(t1[r], curMap.get(t1[r]) + 1);
                    }
                    else                           
                    {
                        curMap.put(t1[r], 1);
                    }
                    
                    if (curMap.get(t1[r]) <= map.get(t1[r]))    
                    {
                        count++;
                    }
                    
                    //advance window by removing extra char
                    while (curMap.get(t1[r]) > map.get(t1[r])) 
                    {
                        curMap.put(t1[l], curMap.get(t1[l]) - 1);
                        l++;
                        if (curMap.get(t1[l]) < map.get(t1[l])) 
                        {
                            count--;
                        }
                    }
                    
                    if (count == total) 
                    {
                        res.add(l);
                        //move sliding window to next
                        curMap.put(t1[l], curMap.get(t1[l]) - 1);
                        l++;
                        count--;
                    }
                }
                else
                {
                    curMap.clear();
                    count = 0;
                    l = r + 1;
                }
            }
            curMap.clear();
        }
        return res;
    }
}

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).