/*

	 *  滑动窗口类型： 模板

	 */

    public List<Integer> slideWindowMode(String s, String t) {

    	// 1 根据题目返回类型定义数据结构

    	ArrayList<Integer> result = new ArrayList<>();

    	if(t.length()> s.length())

    		return result;

    	// 2 新建Map， Key=字符，value=频率

    	HashMap<Character, Integer> map = new HashMap<>();

    	for(char c: t.toCharArray())

    		map.put(c, map.getOrDefault(c, 0) + 1);

    	// 3 定义变量

    	int counter = map.size();	//  目标字符串中的不同字符种类

    	int begin = 0, end = 0;	// 窗口起始、结束点

    	int len = Integer.MAX_VALUE;

    	// 4 源字符串开始遍历

    	while(end < s.length()) {

    		// 5 统计每个字符

    		char c = s.charAt(end);

    		if(map.containsKey(c)) {

    			map.put(c, map.get(c) - 1);

    			if(map.get(c) == 0)

    				counter--;

    		}

    		end++;

    		// 6 符合情况！begin~end 之间包含 t 的所有字符

    		while(counter == 0) { // 此时 Map 的 value 全部 <= 0

    			char tmpc = s.charAt(begin);

    			if(map.containsKey(tmpc)) {

    				map.put(tmpc, map.get(tmpc) + 1);

    				if(map.get(tmpc) > 0)

    					counter++;

    			}

    			// 7 do sth

    			begin++;

    		}

    	}

    	// 8

    	return result;

    }

    public String minWindow(String s, String t) {

		if(t.length()> s.length()) return "";

		HashMap<Character, Integer> map = new HashMap<>();

		for(char c: t.toCharArray())

			map.put(c, map.getOrDefault(c, 0) + 1);

    	int counter = map.size();	//  目标字符串中的不同字符种类

    	int begin = 0, end = 0;	// 窗口起始、结束点

    	int len = Integer.MAX_VALUE;

    	int head = 0;

    	while(end < s.length()) {

    		char c = s.charAt(end);

    		if( map.containsKey(c) ) {

    			map.put(c, map.get(c) - 1);

    			if(map.get(c) == 0)

    				counter--;

    		}

    		end++;

    		while(counter == 0) {	// 此时 Map 的 value 全部 <= 0

    			char tmpc = s.charAt(begin);

    			if( map.containsKey(tmpc) ) {

    				map.put(tmpc, map.get(tmpc) + 1);

    				if(map.get(tmpc) > 0)

    					counter++;

    			}

    			//----------

    			if(end - begin < len) {

    				len = end - begin;

    				head = begin;

    			}

    			//----------

    			begin++;

    		}

    	}

    	if(len == Integer.MAX_VALUE )

    		return "";

    	return s.substring(head, head + len);

    }

	/*

	 * 2、 Longest Substring Without Repeating Characters

	 */

    public int lengthOfLongestSubstring(String s) {

    	HashMap<Character, Integer> map = new HashMap<>();

    	int begin = 0;	// 窗口起始、结束点

    	int max = 0;

    	for (int i = 0; i < s.length(); i++) {

    		char c = s.charAt(i);

    		if(map.containsKey(c)) {

    			max = Math.max(max, i - begin);

    			begin = Math.max(begin, map.get(c) + 1);

    			map.put(c, i);

    		}

    		else {

    			map.put(c, i);

    		}

		}

    	max = Math.max(s.length() - begin, max);

    	return max;

    }

    public List<Integer> findAnagrams(String s, String t) {

        ArrayList<Integer> result = new ArrayList<>();

		if(s.length() < t.length())

			return result;

		HashMap<Character, Integer> map = new HashMap<>();

		for(char c: t.toCharArray())

			map.put(c, map.getOrDefault(c, 0) + 1);

		int counter = map.size();

		int begin = 0, end = 0;

//		int head = 0;

//		int len = Integer.MAX_VALUE;

		while(end < s.length()) {

			char c = s.charAt(end);

			if( map.containsKey(c) ) {

				map.put(c, map.get(c) - 1);

				if(map.get(c) == 0)

					counter--;

			}

			end++;

			while(counter == 0) {

				char tmpc = s.charAt(begin);

				if( map.containsKey(tmpc) ) {

					map.put(tmpc, map.get(tmpc) + 1);

					if(map.get(tmpc) > 0)

						counter++;

				}

				//--------

				if(end - begin == t.length())

					result.add(begin);

				//--------

				begin++;

			}

		}

		return result;

    }