Web Developer

Now the question is how to rob a circular row of houses. It is a bit more complicated to solve than the simpler question. This is because, in the simpler question, whether to rob num[lo] is entirely our choice. However, it is now constrained by whether num[hi] is robbed.

Since we already have a nice solution to the simpler problem, we do not want to discard it. The question then becomes how we can reduce this problem to the simpler one. Extending from the logic that if house i is not robbed, you are free to choose whether to rob house i + 1, you can break the circle by assuming a house is not robbed.

For example, 1 -> 2 -> 3 -> 1 becomes 2 -> 3 if 1 is not robbed.

Since every house is either robbed or not robbed, and at least half of the houses are not robbed, the solution is simply the larger of two cases with consecutive houses, i.e., house i not robbed, break the circle, solve it, or house i + 1 not robbed. Hence, the following solution: I chose i = n and i + 1 = 0 for simpler coding, but you can choose any two consecutive ones.

Here, we’re dividing the string into substrings and checking if they’re palindromes or not. We’re storing all the palindromic substrings in a temporary vector, using the helper function to divide them into substrings. In our helper function, our base condition is if the checking index is equal to the string size, which means we are at the last index, so we simply push back the temporary vector to our answer vector. Otherwise, we’ll check for palindromes in the rest of the string, take a loop, divide it index by index, and check for palindromes. If it’s a palindromic substring, we’ll push it to the answer vector, and then we’ll call the helper function again for the rest. After the function returns, we’ll pop back the element from the temporary vector, which means there is another substring that is not a palindrome. Time complexity: O(n*2^n).

Step 1: I used the brute force approach. At each index, if the element is less than the target, we can always form a combination by picking the current item. The brute force method is based on this idea.

Step 2: I applied the top-down approach using dynamic programming. By drawing the recursion tree, we can see that for a target, we perform the same calculations repeatedly. This can be avoided by storing the number of combinations obtained for a given target, so we don't waste time recalculating it at each recursion.

This can be done by maintaining a DP array where dp[i] denotes the number of combinations possible with target = i. Initially, all elements in the DP array will be initialized to -1, indicating that the number of combinations for that target still needs to be calculated.

Once the number of combinations for sub-target = i (where 0 ≤ i ≤ target) is determined, we can use it to calculate the number of combinations for the larger target.

I also took some help in between whenever I got stuck.

Tip 1 : Be confident
Tip 2 : Always sound positive
Tip 3 : Make sure that you have eye contact and don't ever portray someone as negative person in any situation you are given.