Ad
BaquarAbbas

MinNumberOfCoinsForChange

Given an array of positive integers representing coin denominations and a single non-negative integer n.
representing a target amount of money, write a function that returns the smallest number of coins needed to
make change for (to sum up to) that target amount using the given coin denominations.

Example:

sample Input
n = 7
denoms = [1,5,10]

output = 3//2x1+1x5

time = O(nd),space = O(n).
where n is target amount and d is number of coin denominations

Note: you have access to an unlimited amount of coins.In other words,if denominations are [1,5,10],you have access to unlimited amount of 1s,5s and 10s

If it's impossible to make change for target amount return -1

def minNumberOfCoinsForChange(n, denoms):
	numOfCoins = [float('inf') for amount in range(n+1)]  
	numOfCoins[0] = 0 
	for denom in denoms:
		for amount in range(len(numOfCoins)):
			if denom <= amount:
				numOfCoins[amount] = min(numOfCoins[amount],1+numOfCoins[amount - denom])
	return numOfCoins[n] if numOfCoins[n] != float('inf') else -1
BaquarAbbas

Length of longest palindromic substring

Given a string S of length N, the task is to find the length of the longest palindromic substring from a given string.

Examples:

Input: S = “abcbab”
Output: 5
Explanation:
string “abcba” is the longest substring that is a palindrome which is of length 5.

Input: S = “abcdaa”
Output: 2
Explanation:
string “aa” is the longest substring that is a palindrome which is of length 2.

Note: If the string is empty or None or null then just return 0.do not try to convert the string to lowercase

def length_longest_palindrome(string):
    n = len(string) 
    if n == 0:
        return 0 
    
    maxlen = 1
    table = [[False for i in range(n)]for j in range(n)] 
    for i in range(n):
        table[i][i] = True
        
    start = 0 
    for i in range(n-1):
        if string[i] == string[i+1]:
            table[i][i+1] = True 
            start = i 
            maxlen = 2 
            
    for k in range(3,n+1):
        for i in range(n-k+1):
            j = i + k - 1 
            if table[i+1][j-1] and string[i] == string[j]:
                table[i][j] = True
                
                if k > maxlen:
                    start = i 
                    maxlen = k 
    return maxlen