Member of Technical Staff

A stack can be used to solve this question. 
We traverse the given string s and if we:
1. see open bracket we put it to stack
2. see closed bracket, then it must be equal to bracket in the top of our stack, so we check it and if it is true, we remove this pair of brackets.
3. In the end, if and only if we have empty stack, we have valid string.
Complexity: time complexity is O(n): we put and pop each element of string from our stack only once. Space complexity is O(n).

The brute force solution is to check for every index in the string whether the sub-string can be formed at that index or not. To implement this, run a nested loop traversing the given string and check for sub-string from every index in the inner loop. 
Time Complexity : O(n^2)
The solution can be optimised by using KMP Algorithm. The KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern. The basic idea behind KMP algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of the next window. 
Pseudocode:
Find Prefix:
Begin
length := 0
prefArray[0] := 0

for all character index i of pattern, do
if pattern[i] = pattern[length], then
increase length by 1
prefArray[i] := length
else
if length !=0 then
length := prefArray[length - 1]
decrease i by 1
else
prefArray[i] := 0
done
End
KMP Algorithm:
Begin
n := size of text
m := size of pattern
call findPrefix(pattern, m, prefArray)

while i < n, do
if text[i] = pattern[j], then
increase i and j by 1
if j = m, then
print the location (i-j) as there is the pattern
j := prefArray[j-1]
else if i < n AND pattern[j] != text[i] then
if j != 0 then
j := prefArray[j - 1]
else
increase i by 1
done
End

One approach would be to rotate elements one by one. To rotate by one, store arr[0] in a temporary variable temp, move arr[1] to arr[0], arr[2] to arr[1] …and finally temp to arr[n-1]

leftRotate(arr[], d, n)
start
For i = 0 to i < d
Left rotate all elements of arr[] by one
End
Time complexity : O(n * d) 
Auxiliary Space : O(1)

Another approach would be to use the Reversal Algorithm. Let AB are the two parts of the input array where A = arr[0..d-1] and B = arr[d..n-1]. The idea of the algorithm is: 
• Reverse A to get ArB, where Ar is reverse of A.
• Reverse B to get ArBr, where Br is reverse of B.
• Reverse all to get (ArBr) r = BA.

Algorithm : 

rotate(arr[], d, n)
reverse(arr[], 1, d) ;
reverse(arr[], d + 1, n);
reverse(arr[], 1, n);

Union :
1) Initialize an empty hash set or hash map mp;
2) Iterate through the first array and put every element of the first array in the set mp.
3) Repeat the process for the second array.
4) Print the set mp.

Intersection:
1) Initialize an empty set mp.
2) Iterate through the first array and put every element of the first array in the set mp.
3) For every element x of the second array, do the following :
Search x in the set mp. If x is present, then print it.

Time complexity : O(m+n) under the assumption that hash table search and insert operations take O(1) time.
Space complexity : O(m+n) in case of Union and O(min(m,n)) in case of Intersection