22 posts tagged with "dailychallenge"

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;
    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));
    }
}