SDE - 1

You are given a matrix of 'N' rows and 'M' columns consisting of lowercase characters. You are provided with a string ‘STR,’ and your task is to find the length of the longest consecutive character path for each character in the string ‘STR’. All characters in the path are consecutive, i.e., every character in the path is next to the previous character in alphabetical order. It is allowed to move in all 8 adjacent directions from a cell.

Note:

Suppose you are at position (x, y) then you can move to : [ (x + 1 , y ), ( x - 1 , y ), ( x , y + 1), (x , y - 1), (x + 1, y + 1), (x + 1, y - 1), (x - 1, y + 1), (x - 1, y - 1) ].

For Example:

If ‘N’ = 2, ‘M’ = 2, 'STR’ = "a" and the input matrix is 
[ [ ab ]
  [ ed ] ] 
We need to find the maximum length of the path from starting character ’a’. So the maximum length is 2, which is [a, b]. Hence, the answer is [2].

You are given two positive integers ‘N’ and ‘K’. Your task is to find the smallest ‘N’ digit number whose sum of digits equals ‘K’. If no such number exists then you need to print -1.

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :

If the matrix is 
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4

Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.