class Solution {
    public int myAtoi(String str) {
        if (str==null || str.length()<=0) {
            return 0;
        }
        long res = 0;
        String s = str.trim();
        if (s.length()>0) {
            char[] chars = s.toCharArray();
            int start = 0;
            boolean isPositive =true;

            if (chars[0]=='+') {
                isPositive =true;
                start = 1;
            }else if (chars[0]=='-') {
                isPositive =false;
                start = 1;
            }

            for (int i = start; i < chars.length; i++) {
                
                if (chars[i]>='0' && chars[i]<='9') {
                    res = res*10+chars[i]-'0';
                    if (res>Integer.MAX_VALUE) {
                        return isPositive?Integer.MAX_VALUE :Integer.MIN_VALUE;
                    }
                }
                else{
                    break;
                }
            }

            if (!isPositive) {
                res = 0-res;
            }
        }
        return (int)res;
    }
}

class Solution {
    public int make(char c) {
        switch(c) {
            case ' ': return 0;
            case '+':
            case '-': return 1;
            case '.': return 3;
            case 'e': return 4;
            default://数字情况
                if(c >= 48 && c <= 57) return 2;
        }
        return -1;
    }
    
    public boolean isNumber(String s) {
        int state = 0;
        //最好分类也比较巧妙
        int finals = 0b101101000;
        int[][] transfer = new int[][]{{ 0, 1, 6, 2,-1},
                                       {-1,-1, 6, 2,-1},
                                       {-1,-1, 3,-1,-1},
                                       { 8,-1, 3,-1, 4},
                                       {-1, 7, 5,-1,-1},
                                       { 8,-1, 5,-1,-1},
                                       { 8,-1, 6, 3, 4},
                                       {-1,-1, 5,-1,-1},
                                       { 8,-1,-1,-1,-1}};
        char[] ss = s.toCharArray();
        for(int i=0; i < ss.length; ++i) {
            int id = make(ss[i]);
            if (id < 0) return false;
            state = transfer[state][id];
            if (state < 0) return false;
        }
        return (finals & (1 << state)) > 0;
    }
}

//每个类都实现这个接口
interface NumberValidate { 
    boolean validate(String s);
}
//定义一个抽象类，用来检查一些基础的操作，是否为空，去掉首尾空格，去掉 +/-
//doValidate 交给子类自己去实现
abstract class  NumberValidateTemplate implements NumberValidate{

    public boolean validate(String s)
    {
        if (checkStringEmpty(s))
        {
            return false;
        }

        s = checkAndProcessHeader(s);

        if (s.length() == 0)
        {
            return false;
        }

        return doValidate(s);
    }

    private boolean checkStringEmpty(String s)
    {
        if (s.equals(""))
        {
            return true;
        }

        return false;
    }

    private String checkAndProcessHeader(String value)
    {
        value = value.trim();

        if (value.startsWith("+") || value.startsWith("-"))
        {
            value = value.substring(1);
        }


        return value;
    }



    protected abstract boolean doValidate(String s);
}

//实现 doValidate 判断是否是整数
class IntegerValidate extends NumberValidateTemplate{

    protected boolean doValidate(String integer)
    {
        for (int i = 0; i < integer.length(); i++)
        {
            if(Character.isDigit(integer.charAt(i)) == false)
            {
                return false;
            }
        }

        return true;
    }
}
 
//实现 doValidate 判断是否是科学计数法
class SienceFormatValidate extends NumberValidateTemplate{

    protected boolean doValidate(String s)
    {
        s = s.toLowerCase();
        int pos = s.indexOf("e");
        if (pos == -1)
        {
            return false;
        }

        if (s.length() == 1)
        {
            return false;
        }

        String first = s.substring(0, pos);
        String second = s.substring(pos+1, s.length());

        if (validatePartBeforeE(first) == false || validatePartAfterE(second) == false)
        {
            return false;
        }


        return true;
    }

    private boolean validatePartBeforeE(String first)
    {
        if (first.equals("") == true)
        {
            return false;
        }

        if (checkHeadAndEndForSpace(first) == false)
        {
            return false;
        }

        NumberValidate integerValidate = new IntegerValidate();
        NumberValidate floatValidate = new FloatValidate();
        if (integerValidate.validate(first) == false && floatValidate.validate(first) == false)
        {
            return false;
        }

        return true;
    }

    private boolean checkHeadAndEndForSpace(String part)
    {

        if (part.startsWith(" ") ||
            part.endsWith(" "))
        {
            return false;
        }

        return true;
    }

    private boolean validatePartAfterE(String second)
    {
        if (second.equals("") == true)
        {
            return false;
        }

        if (checkHeadAndEndForSpace(second) == false)
        {
            return false;
        }

        NumberValidate integerValidate = new IntegerValidate();
        if (integerValidate.validate(second) == false)
        {
            return false;
        }

        return true;
    }
}
//实现 doValidate 判断是否是小数
class FloatValidate extends NumberValidateTemplate{

    protected boolean doValidate(String floatVal)
    {
        int pos = floatVal.indexOf(".");
        if (pos == -1)
        {
            return false;
        }

        if (floatVal.length() == 1)
        {
            return false;
        }

        NumberValidate nv = new IntegerValidate();
        String first = floatVal.substring(0, pos);
        String second = floatVal.substring(pos + 1, floatVal.length());

        if (checkFirstPart(first) == true && checkFirstPart(second) == true)
        {
            return true;
        }

        return false;
    }

    private boolean checkFirstPart(String first)
    {
        if (first.equals("") == false && checkPart(first) == false)
        {
            return false;
        }

        return true;
    }

    private boolean checkPart(String part)
    {
        if (Character.isDigit(part.charAt(0)) == false ||
            Character.isDigit(part.charAt(part.length() - 1)) == false)
        {
            return false;
        }

        NumberValidate nv = new IntegerValidate();
        if (nv.validate(part) == false)
        {
            return false;
        }

        return true;
    }
}
//定义一个执行者，我们把之前实现的各个类加到一个数组里，然后依次调用
class NumberValidator implements NumberValidate {

    private ArrayList<NumberValidate> validators = new ArrayList<NumberValidate>();

    public NumberValidator()
    {
        addValidators();
    }

    private  void addValidators()
    {
        NumberValidate nv = new IntegerValidate();
        validators.add(nv);

        nv = new FloatValidate();
        validators.add(nv);

        nv = new HexValidate();
        validators.add(nv);

        nv = new SienceFormatValidate();
        validators.add(nv);
    }

    @Override
    public boolean validate(String s)
    {
        for (NumberValidate nv : validators)
        {
            if (nv.validate(s) == true)
            {
                return true;
            }
        }

        return false;
    }


}
public boolean isNumber(String s) {
    NumberValidate nv = new NumberValidator(); 
    return nv.validate(s);
}

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();
    private int top;
        /** Initialize your data structure here. */
        public MyStack() {

        }
        
        /** Push element x onto stack. */
        public void push(int x) {
            q2.add(x);
            top = x;
            while (!q1.isEmpty()) {                
                q2.add(q1.remove());
            }
            Queue<Integer> temp = q1;
            q1 = q2;
            q2 = temp;
        }
        
        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            q1.remove();
            int res = top;
            if (!q1.isEmpty()) {
                top = q1.peek();
            }
            return res;
        }
        
        /** Get the top element. */
        public int top() {
            return top;
        }
        
        /** Returns whether the stack is empty. */
        public boolean empty() {
            return q1.isEmpty();
        }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

class MyStack {
    private LinkedList<Integer> q1 = new LinkedList<>();

    // Push element x onto stack.
    public void push(int x) {
        q1.add(x);
        int sz = q1.size();
        while (sz > 1) {
            q1.add(q1.remove());
            sz--;
        }
    }

        // Removes the element on top of the stack.
    public int pop() {
        return q1.remove();
    }

        // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }

    // Get the top element.
    public int top() {
        return q1.peek();
    }
    

}

class MyQueue {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    int top;

    /** Initialize your data structure here. */
    public MyQueue() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if (stack1.empty())
            top = x;
        while (!stack1.isEmpty())
            stack2.push(stack1.pop());
        stack2.push(x);
        while (!stack2.isEmpty())
            stack1.push(stack2.pop());

    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        int res = stack1.pop();
        if (!stack1.empty())
            top = stack1.peek();
        return res;
    }

    /** Get the front element. */
    public int peek() {
        return top;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

import java.util.Stack;

public class MyQueue {

    private Stack<Integer> stackPush;
    private Stack<Integer> stackPop;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stackPush = new Stack<>();
        stackPop = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        stackPush.push(x);
    }

    /**
     * 辅助方法：一次性将 stackPush 里的所有元素倒入 stackPop
     * 注意：1、该操作只在 stackPop 里为空的时候才操作，否则会破坏出队入队的顺序
     * 2、在 peek 和 pop 操作之前调用该方法
     */
    private void shift() {
        if (stackPop.isEmpty()) {
            while (!stackPush.isEmpty()) {
                stackPop.push(stackPush.pop());
            }
        }
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        shift();
        if (!stackPop.isEmpty()) {
            return stackPop.pop();
        }
        throw new RuntimeException("队列里没有元素");
    }

    /**
     * Get the front element.
     */
    public int peek() {
        shift();
        if (!stackPop.isEmpty()) {
            return stackPop.peek();
        }
        throw new RuntimeException("队列里没有元素");
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return stackPush.isEmpty() && stackPop.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        while (p!=null|| !stack.isEmpty()) {
            while (p!=null) {
                stack.push(p);
                p=p.left;
            }

            if (!stack.isEmpty()) {
                p = stack.pop();
                res.add(p.val);
                p=p.right;
            }
        }
        return res;
    }
}

class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        //第一层循环表示长度
        for (int i = 2; i <= n; ++i) {
            //第二层循环表示 根从那个开始
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
          }
          return generate_trees(1, n);
    }

    public LinkedList<TreeNode> generate_trees(int start, int end) {
        LinkedList<TreeNode> all_trees = new LinkedList<TreeNode>();
        if (start > end) {
          all_trees.add(null);
          return all_trees;
        }
    
        // 选择一个作为根
        for (int i = start; i <= end; i++) {
          //可能的左子树
          LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);
    
          // 可能的右子树
          LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);
    
          // 两者联系起来
          for (TreeNode l : left_trees) {
            for (TreeNode r : right_trees) {
              TreeNode current_tree = new TreeNode(i);
              current_tree.left = l;
              current_tree.right = r;
              all_trees.add(current_tree);
            }
          }
        }
        return all_trees;
      }

}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
        //这个pre非常巧妙
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root==null) {
            return true;
        }
   
        if(!isValidBST(root.left)){
            return false;
        };

        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        
        return isValidBST(root.right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null && q==null)  return true;
        if(p==null || q==null)return false;

        return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null) {
            return true;
        }
        return IsSymmetric(root.left,root.right);
    }

        boolean IsSymmetric(TreeNode pRoot1,TreeNode pRoot2){
        if (pRoot1==null&&pRoot2==null) {
            return true;
        }

        if (pRoot1==null||pRoot2==null) {
            return false;
        }

        return pRoot1.val==pRoot2.val && IsSymmetric(pRoot1.left,pRoot2.right) && IsSymmetric(pRoot1.right,pRoot2.left) ;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root==null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int nextLevel = 0;
        int toBePrinted = 1;
        ArrayList<Integer> temp = new ArrayList<>();

        while (!queue.isEmpty()) {
            TreeNode p =queue.pop();
            temp.add(p.val);
            toBePrinted--;

            if (p.left!=null) {
                queue.add(p.left);
                nextLevel++;
            }

            if (p.right!=null) {
                queue.add(p.right);
                nextLevel++;
            }
            //说明这一层打印完毕
            if (toBePrinted==0) {
                res.add(temp);
                temp =new ArrayList<>(); 
                toBePrinted = nextLevel;
                nextLevel = 0;
            }
        }
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }

    List<List<Integer>> results = new ArrayList<List<Integer>>();

    // add the root element with a delimiter to kick off the BFS loop
    LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
    node_queue.addLast(root);
      //把null作为结束
    node_queue.addLast(null);

    LinkedList<Integer> level_list = new LinkedList<Integer>();
    boolean is_order_left = true;

    while (node_queue.size() > 0) {
      TreeNode curr_node = node_queue.pollFirst();
      if (curr_node != null) {
        if (is_order_left)
          level_list.addLast(curr_node.val);
        else
          level_list.addFirst(curr_node.val);

        if (curr_node.left != null)
          node_queue.addLast(curr_node.left);
        if (curr_node.right != null)
          node_queue.addLast(curr_node.right);

      } else {
        // we finish the scan of one level
        results.add(level_list);
        level_list = new LinkedList<Integer>();
        // prepare for the next level
        if (node_queue.size() > 0)
          node_queue.addLast(null);
        is_order_left = !is_order_left;
      }
    }
    return results;
  }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  protected void DFS(TreeNode node, int level, List<List<Integer>> results) {
    if (level >= results.size()) {
      LinkedList<Integer> newLevel = new LinkedList<Integer>();
      newLevel.add(node.val);
      results.add(newLevel);
    } else {
      if (level % 2 == 0)
        results.get(level).add(node.val);
      else
        results.get(level).add(0, node.val);
    }

    if (node.left != null) DFS(node.left, level + 1, results);
    if (node.right != null) DFS(node.right, level + 1, results);
  }

  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    DFS(root, 0, results);
    return results;
  }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root==null) {
            return 0;
        }

        TreeNode left = root.left;
        TreeNode right = root.right;

        return Math.max(maxDepth(left), maxDepth(right))+1 ;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder;
    int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder==null || preorder.length==0) {
            return null;
        }
        this.preorder = preorder;
        this.inorder = inorder;
        return BuildTree(0,preorder.length-1,0,inorder.length-1);
    }

        //发现其实这些 end没啥大用，就是为了好理解
    public TreeNode BuildTree(int pStart,int pEnd, int inStart,int inEnd){
        //第一个是根节点
        TreeNode root = new TreeNode(preorder[pStart]);
        if (pStart==pEnd) {
            return root;   
        }
        int i=inStart;
        //从中序遍历中找出根节点，将其分开
        for (; i <=inEnd; i++) {
            if (preorder[pStart] == inorder[i]) {
                break;
            }
        }
        int len = i-inStart;
        if (pStart+1<=pStart+len) 
            root.left = BuildTree(pStart+1,pStart+len,inStart,i-1);
        if (pStart+len+1<=pEnd) 
            root.right = BuildTree(pStart+len+1,pEnd,i+1,inEnd);
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] postorder;
    int[] inorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (postorder==null || postorder.length==0) {
            return null;
        }
        this.postorder = postorder;
        this.inorder = inorder;
        return BuildTree(0,postorder.length-1,0,inorder.length-1);
    }

    public TreeNode BuildTree(int pStart,int pEnd, int inStart,int inEnd){

        //最后一个是根节点
        TreeNode root = new TreeNode(postorder[pEnd]);
        if (pStart==pEnd) {
            return root;   
        }
        int i=inStart;
        //从中序遍历中找出根节点，将其分开
        for (; i <=inEnd; i++) {
            if (postorder[pEnd] == inorder[i]) {
                break;
            }
        }
        int len = i-inStart;
        if (pStart<=pStart+len-1) 
            root.left = BuildTree(pStart,pStart+len-1,inStart,i-1);
        if (pStart+len<=pEnd-1) 
            root.right = BuildTree(pStart+len,pEnd-1,i+1,inEnd);
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] nums;
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums==null||nums.length==0) {
            return null;
        }
        this.nums=nums;
        return creatTree(0, nums.length-1);
    }

    TreeNode creatTree(int start,int end){
        if (start>end) {
            return null;
        }
        int mid = (start+end)/2;
        TreeNode root = new TreeNode(nums[mid]);
        if (start!=end) {
            root.left = creatTree(start,mid-1);
            root.right = creatTree(mid+1,end);
        }
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return IsBalance(root)!=-1;
    }

    private int IsBalance(TreeNode root){
        if(root==null)return 0;
        int left = IsBalance(root.left);
        // -1代表不平衡
        if (left==-1) {
            return -1;
        }
        int right = IsBalance(root.right);
        if (right==-1) {
            return -1;
        }
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root==null) {
            return 0;
        }
        //说明是叶子节点
        if (root.left==null && root.right==null) {
            return 1;
        }

        int left = root.left==null? Integer.MAX_VALUE : minDepth(root.left);
        int right = root.right==null? Integer.MAX_VALUE : minDepth(root.right);

        return Math.min(left, right)+1;
    }
}

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) return res;
        HashMap<String, Integer> map = new HashMap<>();
        int word_length = words[0].length();
        int word_num = words.length;
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        //滑动窗口，分情况
        //将所有移动分成 word_length 类情况，对于单词长度进行遍历
        for (int i = 0; i < word_length; i++) {
            int left = i, right = i, count = 0;
            HashMap<String, Integer> tmp_map = new HashMap<>();
            //每次移动一个单词长度
            while (right + word_length <= s.length()) {
                //得到子串
                String w = s.substring(right, right + word_length);
                right += word_length;
                //判断子串
                if (!map.containsKey(w)) {
                    //不能有其他字符
                    count = 0;
                    //窗口进行滑动
                    left = right;
                    tmp_map.clear();
                } else {
                    tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
                    count++;
                    //发现次数多了
                  //窗口进行滑动，一直移除单词，直到次数符合了
                    while (tmp_map.getOrDefault(w, 0) > map.getOrDefault(w, 0)) {
                        String t_w = s.substring(left, left + word_length);
                        count--;
                        tmp_map.put(t_w, tmp_map.getOrDefault(t_w, 0) - 1);
                        left += word_length;
                    }
                    if (count == word_num) res.add(left);
                }
            }
        }
        return res;
    }
}

class Solution {
    //记录原字符中出现的次数
    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    //记录窗口中单词出现的次数
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
        int tLen = t.length();
        //初始化
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        
        while (r < sLen) {
            ++r;
            //如果包含则加入，r右滑动
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            //检查成功
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                //l右滑，缩小窗口
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }
	//检查l到r是否包含子串
    public boolean check() {
        Iterator iter = ori.entrySet().iterator(); 
        while (iter.hasNext()) { 
            Map.Entry entry = (Map.Entry) iter.next(); 
            Character key = (Character) entry.getKey(); 
            Integer val = (Integer) entry.getValue(); 
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        } 
        return true;
    }
}