public  String longestPalindrome(String s) {
        int n = s.length();
        if(n == 1){
            return s;
        }
        String res;
        for(int i = n;i > 0;i--){
            for(int j = 0;j <= n - i;j++){
                res = s.substring(j,i + j);
                StringBuilder str = new StringBuilder();
                str.append(res);
                if(str.reverse().toString().equals(res)){
                    return res;
                }
            }
        }
        return null;
        int n = s.length();
        if (n == 1) {
            return s;
        }
        if(n == 2){
            if(s.charAt(0) == s.charAt(1)){
                return s;
            }else {
                return s.substring(0,1);
            }
        }
        int len = 0;
        int left = 0;
        int right = 0;
        String res = "";
        for (int i = 1; i < n ; i++) {
            left = i;
            right = i;
            String s1 = "",s2 = "" ;
            s1 = isPalindrome(s,left,right);
            if(s.charAt(left-1) == s.charAt(right)){
                s2 = isPalindrome(s,left-1,right);
            }
            if(len < s1.length()){
                len = s1.length();
                res = s1;
            }
            if(len < s2.length()){
                len = s2.length();
                res = s2;
            }
        }
        return res;
    }
    public static String isPalindrome(String s,int left,int right){
        int n = s.length();
        int len = right - left + 1;
        String res = s.substring(left,right + 1);
        while(left >= 0 && right <= n-1){
            if(s.charAt(left) != s.charAt(right))
                break;
            if((right - left + 1) > len){
                len = right - left + 1;
                res = s.substring(left,right + 1);
            }
                left--;
                right++;
            }
        return res;
    }

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

class Solution {
    public ArrayList<ArrayList<String>> all = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();
        res.add("()");
        if(n == 1){
            return res;
        }
        all.add(res);
        for (int i = 2; i <= n; i++) {
            res = add(res,i);
            ArrayList<String> temp = new ArrayList<>();
            temp.addAll(res);
            all.add(temp);
        }
        return res;
    }
    public ArrayList add(ArrayList<String> list,int size){
        ArrayList res = new ArrayList();
        HashSet<String> set = new HashSet();
        for(String i : list){
            set.add("()"+i);
            set.add(i+"()");
            set.add("("+i+")");
            set.remove(i);
        }
        if(size >= 4){
            for (int i = 2; i <= size - 2; i++) {
                int j = size - i;
                for (String s1 : all.get(i - 1)){
                    for(String s2 : all.get(j - 1)){
                        set.add(s1+s2);
                    }
                }
            }
        }
        Object[] strs =set.toArray();
        for(Object i : strs){
            res.add((String)i);
        }
        return res;
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        Stack<Character> stack = new Stack();
        int res = 0,temp = 0;
        int len = s.length();
        int[] arr = new int[len];
        int i = 0;
        while(i < len){
            int size = stack.size();
            if(size == 0){
                stack.push(s.charAt(i));
                arr[i] = 1;
                i++;
                continue;
            }
            if(size > 0 && stack.peek() == '(' && s.charAt(i)==')'){
                stack.pop();
                arr[i] = 0;
                for(int j = i;j >= 0;j--){
                    if(arr[j] == 1){
                        arr[j] = 0;
                        break;
                    }
                }
            }else {
                stack.push(s.charAt(i));
                arr[i] = 1;
            }
            i++;
        }
        for (int j = 0; j < arr.length; j++) {
            if(arr[j] == 0){
               temp++;
               res = res > temp ? res : temp;
            }else {
                temp = 0;
            }
        }
        return res;
    }
}

class Solution {
    public int trap(int[] height) {
        if(height.length <= 1 ){
            return 0;
        }
        int left = 0,right = 0;
        for (int i = 0; i < height.length; i++) {
            if(height[i] > height[left]){
                left = i;
            }
        }
        for (int i = 0; i < height.length; i++) {
            if(height[i] > height[right] && i != left){
                right = i;
            }

        }
        if(left > right){
            right = left + right;
            left = right - left;
            right = right - left;
        }
        return add(left,right,height)+leftsum(0,left,height)+rightsum(right,height.length-1,height);

    }
    public int leftsum(int left,int right,int[] height){
        if(left+1 >= right){
            return 0;
        }
        int index = 0;
        for(int i = 0;i < right;i++){
            if(height[index] < height[i]){
                index = i;
            }
        }
        return add(index,right,height)+leftsum(0,index,height);
    }
    public int rightsum(int left,int right,int[] height){
        if(left+1 >= right){
            return 0;
        }
        int index = left+1;
        for(int i = left+1;i < height.length;i++){
            if(height[index] < height[i]){
                index = i;
            }
        }
        return add(left,index,height)+rightsum(index,right,height);
    }
    public int add(int left,int right,int[] height){
        if(left + 1 >= right){
            return 0;
        }
        int min = Math.min(height[left],height[right]);
        if(min == 0){
            return 0;
        }
        int sum = 0;
        for(int i = left + 1;i < right;i++){
            sum += min - height[i];
        }
        return sum;
    }
}

class Solution {
    public int jump(int[] nums) {
        int res = 0;
        int len = nums.length;
        for (int i = 0; i < len - 1;) {
            int max = -1;
            int nexPos = -1;
            for (int j = nums[i]; j >= 1; j--) {
                if(i + j >= len - 1){return ++res;}
                int nextNum = nums[i + j];
                if(j + nextNum >= max){
                   max = j + nextNum;
                   nexPos = i + j;
                }
            }
            i = nexPos;
            res++;
        }
        return res;
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        int k = 0;
        for(int i = 0; i < nums.length; i++) {
            if (i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true;
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];
        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }
        return f[m - 1];
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(i - 1 >= 0 && j - 1 >= 0) grid[i][j] += Math.min(grid[i - 1][j],grid[i][j - 1]);
                else if (i - 1 >= 0) grid[i][j] += grid[i - 1][j];
                else if (j - 1 >= 0) grid[i][j] += grid[i][j - 1];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        int[] num = new int[n];
        num[0] = 1;
        num[1] = 2;
        for(int i = 2;i < n;i++){
            num[i] = num[i-1] + num[i-2];
        }
        return num[n-1];

    }
}