# LeetCode 650. 2 Keys Keyboard: Java Solution

## Problem Statement

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy: You can copy all the characters present on the notepad (partial copy is not allowed). Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

``````Function Signature (Java):
int minSteps(int n)

Inputs:
3

Outputs:
3

Intitally, we have a single 'A'.
In step 1, we copy:
A
In step 2, we paste:
AA
In step 3, we paste again:
AAA
``````

## TL;DR Code Solution

``````public int minSteps(int n) {
int[] dp = new int[n+1];

for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = i-1; j > 1; j--) {
if (i % j == 0) {
dp[i] = dp[j] + (i/j);
break;
}

}
}
return dp[n];
}
``````

# LeetCode 3Sum: C++ Solution

## TL;DR Code Solution

``````vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;

for (int i = 0; i < (int)nums.size() - 2; i++) {
int pin = nums[i];
int left = i + 1;
int right = (int)nums.size() - 1;
while (left < right) {
if (pin + nums[left] + nums[right] == 0) {
int numLeft = nums[left];
int numRight = nums[right];
vector<int> current = {pin, nums[left], nums[right]};
result.push_back(current);

while (left < right && nums[left] == numLeft)
left++;

while (left < right && nums[right] == numRight)
right--;
}
else if (pin + nums[left] + nums[right] < 0) {
left++;
}
else {
right--;
}
}

while (i + 1 < nums.size() && nums[i + 1] == nums[i])
i++;

}

return result;

}

``````

# LeetCode 259. 3 Sum Smaller: C++ Solution

## Problem Statement

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

``````Function Signature (C++):
int threeSumSmaller(vector<int>& nums, int target)

Inputs:
nums = [-2, 0, 1, 3]
target = 2

Outputs:
2

Two triplets with sums less than 2 can be created:
[-2, 0, 1]
[-2, 0, 3]
``````

## TL;DR Code Solution

``````int threeSumSmaller(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());

int count = 0;
for (int i = 0; i < (int)nums.size() - 1; i++) {
int pin = nums[i];
int right = (int)nums.size() - 1;
int left = i + 1;
while (left < right) {
int sum = pin + nums[left] + nums[right];
if (sum < target) {
count += right - left;
left++;
}
else {
right--;
}
}
}
return count;
}
``````

# LeetCode 18. 4Sum: CPP Solution

## Problem Statement

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

``````Function Signature (C++):
vector<vector<int>> fourSum(vector<int>& nums, int target)

Inputs:
nums = [1, 0, -1, 0, -2, 2]
target = 0

Outputs:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]
``````

## TL;DR Code Solution

``````vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());

vector<vector<int>> result;

int size = (int)nums.size();
for (int i = 0; i < size - 3; i++) {
int first = nums[i];
for (int j = i + 1; j < size - 2; j++) {
int second = nums[j];
int left = j + 1;
int right = size - 1;
while (left < right) {
int numLeft = nums[left];
int numRight = nums[right];

int sum = first + second + nums[left] + nums[right];
if (sum == target) {
vector<int> current = {first, second, nums[left], nums[right]};
result.push_back(current);

while (left < right && nums[left] == numLeft)
left++;
while (left < right && nums[right] == numRight)
right--;
}
else if (sum < target) {
left++;
}
else {
right--;
}
}
while (j + 1 < size  - 2 && nums[j+1] == nums[j])
j++;
}
while (i + 1 < size  - 3 && nums[i+1] == nums[i])
i++;
}

return result;
}
``````

# LeetCode 454. 4Sum II: C++ Solution

## Problem Statement

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

``````Function Signature (C++):
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D)

Inputs:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Outputs:
2

We can create two different tuples:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
``````

## TL;DR Code Solution

``````int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> sums;
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
sums[A[i] + B[j]]++;
}
}

int count = 0;
for (int i = 0; i < C.size(); i++) {
for (int j = 0; j < D.size(); j++) {
if (sums.find(-(C[i] + D[j])) != sums.end()) {
count += sums[-(C[i] + D[j])];
}
}
}

return count;
}
``````

# LeetCode 454. 4Sum II: CPP Solution

## Problem Statement

Given a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict.

If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

``````Function Signature (C++):

Inputs:
s = "abcxyz123"
dict = ["abc","123"]

Outputs:
"<b>abc</b>xyz<b>123</b>"

Inputs:
s = "aaabbcc"
dict = ["aaa","aab","bc"]

Outputs:
"<b>aaabbc</b>c"
``````

## TL;DR Code Solution

``````string addBoldTag(string s, vector<string>& dict) {

vector<bool> isBold(s.length());
for (int i = 0; i < dict.size(); i++) {
int searchIndex = s.find(dict[i], 0);
while (s.find(dict[i], searchIndex) != std::string::npos) {
for (int j = searchIndex; j < searchIndex + dict[i].length(); j++) {
isBold[j] = true;
}
searchIndex = s.find(dict[i], searchIndex + 1);
}

}

int runner = 0;
string result;
while (runner < s.length()) {
if (!isBold[runner]) {
result += s[runner];
runner++;
}
else {
result += "<b>";
while (runner < s.length() && isBold[runner]) {
result += s[runner];
runner++;
}
result += "</b>";
}
}

return result;
}
``````