class Solution {
    int[] memo;
    int MOD = 1000000007;
    public int numberOfArrays(String s, int k) {
        memo = new int[s.length() + 1];
        Arrays.fill(memo,-1);
        return dp(s,k,0);
    }
    private int dp(String s, int k, int curr){
        // base case 
        if(curr == s.length()) return 1; // we have no more possible number to play with
        if(s.charAt(curr) == '0') return 0; // leading zero
        // solved case
        if(memo[curr] != -1) return memo[curr];
        // start res with 0
        int res = 0;
        for(int i = curr; i < s.length(); i ++){
            // try pairtition at every possible point
            String num = s.substring(curr,i + 1);
            // if num > k then we know we cant have this number
            if (Long.parseLong(num) > k)
                break;
            // add to res if we made to the end (+ 1) res
            res = (res + dp(s,k,i + 1)) % MOD;

        }
        return memo[curr] = res;
    }
}

class Solution {
    Integer[][] memo;
    int min = Integer.MAX_VALUE;
    int start = -1;
    public String minWindow(String s1, String s2) {
        memo = new Integer[s1.length()][s2.length() + 1];
        dp(s1,s2,0,0);
        return start == -1 ? "" : s1.substring(start,start + min);
    }
    private int dp(String s1, String s2, int p1, int p2){ 
        // we use dp method to find the ending index at given index of s1 

        if(p2 == s2.length()) return p1; // we have all the character from p2
        if(p1 == s1.length()) return Integer.MAX_VALUE; // we are not able to match 
        // solved case
        if(memo[p1][p2] != null) return memo[p1][p2];
        // solve the case 
        // starts with skip the character
        int res = dp(s1,s2,p1 + 1, p2);
        if(s1.charAt(p1) == s2.charAt(p2)){
            // we have a match 
            res = Math.min(res,dp(s1,s2,p1 + 1, p2 + 1));
        }
        if(p2 == 0 && res < Integer.MAX_VALUE){
            // this is a valid starting point 
            // note since we called skip first, that means we are always replacing the substring as we moving forward 
            // so res - p1 <= min is important here to locate the correct starting point
            if(res - p1 <= min){
                min = res - p1;
                start = p1;
            }
        }
        return memo[p1][p2] = res;
    }

class Solution {
    Integer[][] memo;
    public int minInsertions(String s) {
        // we can think this as in a different prespective 
        // what is longest we have to insert to make this a palindrome?
        // that is correct we can insert s in reverse to complish that, 
        // if we take out the character we already have that means everthing else would then become palindrome 
        memo = new Integer[s.length()][s.length()];
        StringBuilder sb = new StringBuilder(s);
        
        return s.length() - lcs(s,sb.reverse().toString(),0,0);
    }
    private int lcs(String s1, String s2, int p1, int p2){
        // base case 
        // case if we used one of the string up 
        if(p1 == s1.length()) return 0;  
        if(p2 == s2.length()) return 0; 
        // solved case
        if(memo[p1][p2] != null) return memo[p1][p2];
        // solve the case 
        
        if(s1.charAt(p1) == s2.charAt(p2)){
            // if we have a match 
            return memo[p1][p2] =  1 + lcs(s1,s2,p1 + 1,p2 + 1);
        }
        return memo[p1][p2] = Math.max(lcs(s1,s2,p1 + 1,p2),lcs(s1,s2,p1,p2 + 1));
    }
}