# Daily Coding Challenge #29

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

/*
LeetCode - Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:

Input: amount = 10, coins = [10]
Output: 1
*/

class Solution {
public:
int change(int amount, vector<int>& coins) {
// unbounded knapsack
vector<int> dp(amount+1,0);
dp[0]=1;
for(auto c:coins){
for(int j=c;j<=amount;j++){
dp[j]+=dp[j-c];
}
}
return dp[amount];
}
};

/*
LeetCode - Power of Two

Given an integer, write a function to determine if it is a power of two.

Example 1:

Input: 1
Output: true
Explanation: 20 = 1
Example 2:

Input: 16
Output: true
Explanation: 24 = 16
Example 3:

Input: 218
Output: false
*/

class Solution {
public:
bool isPowerOfTwo(int n) {
// 8(n): 00001000
// 7(n-1): 00000111
// 8&7 (n&n-1) = 00000000 = 0
return n>0&&!(n&(n-1));
}
};

/*
LeetCode - Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
*/

class Solution {
public:
bool isSubsequence(string s, string t) {
int ssz=(int)s.size();
int tsz=(int)t.size();
int i=0,j=0;
// two pointer approach
for(;i<ssz&&j<tsz;j++){
// if matched, move i to the next char in s
if(s[i]==t[j]) i++;
}
// if i reaches the end, it means it is a subseqeunce
return (i==ssz);
}
};

class Solution2 {
public:
bool isSubsequence(string s, string t) {
// DP approach - similar to 1143. Longest Common Subsequence
int m=(int)s.size(), n=(int)t.size();
if(m==0) return true;
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s[i-1]==t[j-1]) {
dp[i][j]=dp[i-1][j-1]+1;
} else {
dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n]==m;
}
};

static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

The source code is available in corresponding repo below. Star and watch for timely updates!