SDE - 1

You are given an integer n, which defines an n x n binary grid. Initially, all values in the grid are 1s. You are also given an array mines, where each element mines[i] = [row, col] indicates that the cell grid[row][col] should be a 0.

Your task is to find the order of the largest axis-aligned plus sign of 1s contained in the final grid. If no plus sign of 1s exists (i.e., the grid contains no 1s), you should return 0.

An axis-aligned plus sign of order k is defined by:

  A center cell grid[r][c] which must be 1.
  Four "arms" of 1s extending up, down, left, and right from the center.
  The length of each arm must be at least k-1.

This means the order k is determined by the shortest arm extending from the center. For a plus sign centered at (r, c), the order is 1 + min(up, down, left, right), where up is the number of consecutive 1s above the center, down is the number below, and so on.

You are given a string ‘S’ containing only the characters ‘)’ and ‘(‘. You need to find the length of the longest valid i.e. well-formed parentheses substring.

For example:

Let the given string be “(()())((”.

Here the valid parentheses substrings are: “()”, “()” and “(()())”. Out of these the longest valid string is “(()())” which has a length 6.