SDE - Intern

Approach : 

Every node has two options either it can have a camera or it cannot. If a node has a camera, then it definitely covers itself, and if it doesn’t have a camera then there are two options either the children nodes cover the current node or the parent node covers the current node. 

A node can be of three types-

Case - 0: ‘CURRENT_NODE’ is not monitored but all nodes in the subtree are monitored.
Case - 1: ‘CURRENT_NODE’ is monitored but no camera. All nodes in the subtree of this node are also monitored.
Case - 2: ‘CURRENT_NODE’ has a camera and all nodes in the subtree are monitored.


Algorithm : 

1) Do a depth-first-search on the binary tree which returns an array of size three, denoting the number of cameras corresponding to the three cases mentioned above.

2) If the ‘CURRENT_NODE’ is null then return {0, 0, 1}, since for the leaf node we want ‘CASE2’ to be 1 as it is never optimal to place a camera on a leaf node.

3) Do a depth-first search on the left subtree, and save the result to ‘LEFT_CHILD’.

4) Do a depth-first search on the right subtree, and save the result to ‘RIGHT_CHILD’.

5) Initialize ‘CASE0’ to LEFT_CHILD[1] + RIGHT_CHILD[1], since the ‘CURRENT_NODE’ is not monitored, so the most optimal choice will be that both the children nodes should be monitored but should have no camera.

6) Initialize ‘CASE1’ to min( LEFT_CHILD[2] + min(RIGHT_CHILD[1], RIGHT_CHILD[2]), RIGHT_CHILD[2] + min(LEFT_CHILD[1], LEFT_CHILD[2]), since the ‘CURRENT_NODE’ is monitored but it has no camera means at least one of the children nodes should have a camera.

7) Initialize ‘CASE2’ to 1 + min(LEFT_CHILD[0], LEFT_CHILD[1], LEFT_CHILD[2]) + min(RIGHT_CHILD[0], RIGHT_CHILD[1], RIGHT_CHILD[2]).

8) Return {CASE0, CASE1, CASE2}.

TC : O(N) where N=total number of nodes in the binary tree
SC : O(N)

Approach :
1) Create a 2-D dp boolean vector(with all false initially) where dp[i][j] states whether s[i...j] is a palindrome or not and initilialise a variable ans=1 which will store the final answer.

2) Base Case : For every i from 0 to n-1 fill dp[i][i]=1 ( as a single character is always a palindrome ) .

3) Now, run 2 loops first one from i=n-1 to i=0 (i.e., tarverse from the back of the string) and the second one from
j=i+1 to n .

4) For every s[i]==s[j] , check if(j-i==1 i.e., if s[i] and s[ j] are two consecutive same letters) or if(dp[i+1][j-1]==1 or not
i.e., if the string s[i+1,....j-1] is palindrome or not .

5) Because if the string s[i+1,....j-1] is a palindrome and s[i]==s[j] then s[i] and s[j] can be appended at the starting
and the ending position of s[i+1,...j-1] and s[i...j] will then be a palindrome , so mark dp[i][j]=1 and update the answer as ans=max(ans , j-i+1). 

6) Finally return the ans

TC : O(N^2) where N=length of the string s
SC : O(N^2)