Coding Problems and Solutions — 14

[1] Find Longest Awesome Substring — Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

Example:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

(https://leetcode.com/problems/find-longest-awesome-substring/)

Approach — A substring is palindrome if all the numbers occurs even number of times or only one number occurs odd number of times.

Let ‘n’ represent the integer corresponding to the bit vector whether count of the digit k is even or odd.

‘0010100010’ is the bit vector indicating that counts of digits 1, 5 and 7 are odd and the rest are even.

At each index i, update n by toggling the s[i]-th bit because if count of s[i] increments by 1 the bit toggles.

Keep a map from n to the last i.

If all the digits in the palindrome i to j occurs even number of times then n(i) = n(j+1). Thus check if n(i) has been seen earlier.

To check if any one digit occurs in odd number of times, for each digit j toggle the j-th bit in n(i) (call it m(i)) and check if we have seen m(i) earlier.

[2] Get the Maximum Score — You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

• Choose array nums1 or nums2 to traverse (from index-0).
• Traverse the current array from left to right.
• If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

(https://leetcode.com/problems/get-the-maximum-score/)

Approach — Use merge sort technique starting from end of the both arrays. Idea is to compute a map x[a] where x[a] is the maximum sum path starting with value ‘a’. If ‘a’ occurs in both arrays, then compute maximum.

Instead of extra space map, we use two variables because we only need the next number from both arrays.

[3] Maximum Number of Non-Overlapping Subarrays With Sum Equals Target — Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

(https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/)

Approach — Use DP.

‘sum_pos’ is a map from current sum to the latest index where sum (i to len(nums)-1) occurs.

cnts[] is an array where cnts[i] is the maximum number of non-overlapping sub-arrays in the region i to len(nums)-1.

[4] Minimum Cost to Cut a Stick — Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.

Return the minimum total cost of the cuts.

Example:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).

(https://leetcode.com/problems/minimum-cost-to-cut-a-stick/)

Approach — Use recursion with DP.

[5] Range Sum of Sorted Subarray Sums —given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

Example:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.

(https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/)

Approach — Use binary search to find sum of all numbers less than equal to left and right. Then subtract right-left.

Use logic of finding kth smallest number to find left-th and right-th smallest numbers. But instead of finding the left-th and right-th, find the sums.

[6] Find Kth Bit in Nth Binary String — Given two positive integers n and k, the binary string Sn is formed as follows:

• S1 = "0"
• Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

Example:

Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".

(https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/)

Approach — Use recursion.

[7] Can Convert String in K Moves — Given two strings s and t, your goal is to convert s into t in k moves or less.

During the ith (1 <= i <= k) move you can:

• Choose any index j (1-indexed) from s, such that 1 <= j <= s.length and j has not been chosen in any previous move, and shift the character at that index i times.
• Do nothing.

Shifting a character means replacing it by the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Shifting a character by i means applying the shift operations i times.

Remember that any index j can be picked at most once.

Return true if it's possible to convert s into t in no more than k moves, otherwise return false.

Example:

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.

(https://leetcode.com/problems/can-convert-string-in-k-moves/)

Approach — If the count of the difference x=(t[i]-s[i])%26 for any i is y, then k should be at-least 26*(y-1)+x. If this fails for any difference x, then return False.

[8] Minimum Insertions to Balance a Parentheses String — Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:

• Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
• Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.

For example, "())", "())(())))" and "(())())))"are balanced, ")()", "()))" and "(()))" are not balanced.

You can insert the characters ‘(‘ and ‘)’ at any position of the string to balance it if needed.

Return the minimum number of insertions needed to make sbalanced.

Example:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.

(https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/)

Approach — Use stack.

If the last parenthesis is ‘)‘ and 2nd last is ‘(‘ then if the current is ‘)’, remove the last 2 but don’t add the current into stack.

Else if current is ‘(‘, then remove the last 2 and add 1 to counts because one ‘)’ is missing. Also add the current ‘(‘ parenthesis.

If last is ‘)‘ and if current is ‘)’, add 1 to counts (one missing ‘(‘) and don’t add the current parenthesis to stack, else if it is ‘(‘ then add 2 (one missing ‘(‘ and one ‘)’).

[9] Minimum Number of Days to Eat N Oranges — There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

• Eat one orange.
• If the number of remaining oranges (n) is divisible by 2 then you can eat n/2 oranges.
• If the number of remaining oranges (n) is divisible by 3 then you can eat 2*(n/3) oranges.

You can only choose one of the actions per day.

Return the minimum number of days to eat n oranges.

Example:

Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

(https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/)

Approach — Use DP with recursion.

If n is a power of 2 or 3, then return the base + 1 (use int(log(n))+1).

If n is divisible by 6, then divide by 3.

If n is divisible by 2 only, then either divide by 2 or subtract the required number of oranges that is divisible by 3 and then divide by 3.

If n is divisible by 3 only, then either divide by 3 or subtract the required number of oranges that is divisible by 2 and then divide by 2.

Else either subtract the required number of oranges that is divisible by 3 and then divide by 3 or subtract the required number of oranges that is divisible by 2 and then divide by 2.

[10] Magnetic Force Between Two Balls — In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

Example:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

(https://leetcode.com/problems/magnetic-force-between-two-balls/)

Approach — Use binary search over the minimum force required. For each force check the minimum number of balls that is required for that force. If minimum balls is greater than ‘m’ then decrease the force else increase.

Place the 1st ball in the first basket, then next ball in the basket that is at-least ‘min-force’ distance away from first basket and so on. Check how many balls can be placed in such a way.

[11] Subtree of Another Tree — Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example:
Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

(https://leetcode.com/problems/subtree-of-another-tree/)

Approach — Tree ‘t’ is subtree of ‘s’ if the in-order traversal of t is a substring of the in-order traversal of s and preorder/postorder traversal of t is a substring of the preorder/postorder traversal of s.

Also for in-order, preorder or postorder traversal, replace missing node with ‘_’ special character.