Java Sliding Window

  • 3

    Idea is to keep a window of size p.length() and check if the substring is valid among the way.

    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            if(p.length() > s.length())
                return res;
            char[] sStr = s.toCharArray();
            int[]map = new int[26];
            for(char ch:p.toCharArray())
                map[ch - 'a']++;
            int n = s.length(), m = p.length();;
            int j = 0;
            for(j=0; j<m-1; j++)
                map[sStr[j] - 'a']--;
            for(int i=0; j<n; i++, j++){
                map[sStr[j] - 'a']--;
                map[sStr[i] - 'a']++;
            return res;
        public boolean check(int[]map){
            for(int n:map)
                if(n > 0)   return false;
            return true;

  • 1

    how about the time complexity?

  • 0

    @yuhengw I think it is O(n), since 26 is a constant.

Log in to reply

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