SDE - 1

Given a string (STR) of length N, you have to create a new string by performing the following operation:

Take the smallest character from the first 'K' characters of STR, remove it from STR and append it to the new string.

You have to perform this operation until STR is empty.

 Note:

The input string(STR) will not contain any spaces.

Assume that all characters in STR are lower case letters.

If characters less than 'K' remain, then append them in a sorted way to the new string.

Example:

Let the input string be "edcba" with K = 4.

Let the new string to be formed is initially empty, newString = "".
The first set of 4 characters are, ('e', 'd', 'c', 'b')
Out of these 4 characters, the smallest one is 'b' and hence we add it to the newString and it becomes, 
newString = "b"

The next set of 4 characters are, ('e', 'd', 'c', 'a')
Out of these 4 characters, the smallest one is 'a' and hence we add it to the newString and it becomes, 
newString = "ba"

Now we are left with "edc" and since we can't get a window of size 4, we sort them in the increasing order and append them to the newString.

Hence, newString thus formed will be "bacde".

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

You are given an array/list of ‘N’ integers. You are supposed to return the maximum sum of the subsequence with the constraint that no two elements are adjacent in the given array/list.

Note:

A subsequence of an array/list is obtained by deleting some number of elements (can be zero) from the array/list, leaving the remaining elements in their original order.

You have been given a long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Example:

Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

You are given an unweighted directed graph of 'V' vertices and 'E' edges. Your task is to print all the strongly connected components (SCCs) present in the graph.