Shortest/Concise JAVA O(n) Sliding Window Solution


  • 0
    K

    @carlyleliang Try to think without count. You have to update hash while left pointer/right pointer moving to right, so values in hash have nothing related to count. Also, if you could understand how to move right pointer to right, you should be able to figure out how left pointer works. Check the codes, they are almost mirror.


  • 0
    K

    @NathanNi said in Shortest/Concise JAVA O(n) Sliding Window Solution:

    if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++;

    I think you should run this line at the beginning of the loop, or change it to (right - left + 1 == p.length()), otherwise, you are counting p.length() + 1 chars.

    Actually you don't have to maintain left, left can be inferred by right - p.length() + 1


  • 0
    N

    @krisdu Many thanks for the revise, the original code is extremely unreadable


  • 0

    @krisdu easy to understand, thank you.


  • 0
    L

    Short C++ solution

    vector<int> findAnagrams(string s, string p) {
        int n=p.size(), count=0;
        vector<int> dict(26,0), res;
        for(int i=0;i<n;i++) dict[p[i]-'a']++;
        for(int b=-n+1, e=0; e<s.size(); e++,b++){	
            if(dict[s[e]-'a']-- >0) count++;
            if(count==n) res.push_back(b);
            if(b>=0 && dict[s[b]-'a']++ >=0) count--;
        }
        return res;   
    }
    

  • 0
    J

    @krisdu said in Shortest/Concise JAVA O(n) Sliding Window Solution:

    s.length() == 0 || p == null || p.length() == 0) return list;

    great solution, just can't believe this is an easy question......


  • -1
    L

    What if string p contains duplicated character ? count = p.length() could be wrong under this situation.


  • 0
    A

    @krisdu cleaner version, thanks


  • 0
    S

    thanks a lot!
    here is a swift version

    func getHash(_ c: Character) -> Int {
        return Int(c.unicodeScalars.first!.value)
    }
    
    func findAnagrams(_ s: String, _ p: String) -> [Int] {
        var res = [Int]()
        var hash = [Int](repeating: 0, count: 256)
        var s = Array(s), p = Array(p)
        
        for c in p {
            hash[getHash(c)] += 1
        }
        
        var left = 0 , right = 0 , count = p.count
        while right < s.count {
            if hash[getHash(s[right])] >= 1 {
                count -= 1
            }
            hash[getHash(s[right])] -= 1
            right += 1
            
            if count == 0 { res.append(left) }
    
            if right - left == p.count {
                if hash[getHash(s[left])] >= 0 {
                    count += 1
                }
                hash[getHash(s[left])] += 1
                left += 1
            }
        }
        return res
    }
    

  • 0
    A

    @krisdu said in Shortest/Concise JAVA O(n) Sliding Window Solution:

    Can anyone pls tell why we did this:

    if (hash[s.charAt(left)] >= 0) {
    count++;
    }
    hash[s.charAt(left)]++;


Log in to reply
 

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