CODEWITHSUNDEEP
algorithmtime-complexity
codereviewanskquestions
codereviewanskquestions

Reputation: 13998

Sliding window time complexity

I have this sliding window algorithms for problem;Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. People said the running time of this algorithm is o(len(s)) and I'd like to make sure that if I understand it correctly.

So the outer while is o(len(s)) (assume map look up is o(1)) and the inner while loop also can run for o(len(s)) in worst case. For exmaple, if S is axyzzzzzzzbc and P is abc then the inner while loop moves the start pointer to the end so it will be o(len(s) + len(s)) so it's o(2len(s)) but we drop constant so the final run time is o(len(s)).

Please let me know if this is correct.

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ret = new ArrayList<>();
    Map<Character, Integer> map = new HashMap<>();
    for (Character c : p.toCharArray()) {
        map.put(c, map.get(c) == null ? 1 : map.get(c) + 1);
    }
    int b = 0, i = 0;
    int c = map.size();
    while (i < s.length()) {
        if (map.containsKey(s.charAt(i))) {
            int t = map.get(s.charAt(i)) - 1;
            map.put(s.charAt(i), t);
            if (t == 0) c--;
        }
        i++;
        while (c == 0) {
            if (map.containsKey(s.charAt(b))) {
                int t = map.get(s.charAt(b)) + 1;
                map.put(s.charAt(b), t);
                if (t > 0) c++;
                    c++;
            }
            if (i - b == p.length()) {
                ret.add(b);
            }
            b++;

        }
    }
    return ret;

Upvotes: 1

Views: 6163

Answers (1)

MBo
MBo

Reputation: 80267

Yes, complexity is linear. Most chars are treated twice - except for last M=p.length-1 ones.

So O(N + N - M) = O(N)

Upvotes: 1

Related Questions