A valid parentheses string is either empty " ", "( " + A + ") ", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.
" ", "() ", "(())() ", and "(()(())) " are all valid parentheses strings.A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.
Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.
Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.
Example 1:
Input: s = "(()())(()) " Output: "()()() " Explanation: The input string is "(()())(()) ", with primitive decomposition "(()()) " + "(()) ". After removing outer parentheses of each part, this is "()() " + "() " = "()()() ".
Example 2:
Input: s = "(()())(())(()(())) " Output: "()()()()(()) " Explanation: The input string is "(()())(())(()(())) ", with primitive decomposition "(()()) " + "(()) " + "(()(())) ". After removing outer parentheses of each part, this is "()() " + "() " + "()(()) " = "()()()()(()) ".
Example 3:
Input: s = "()() " Output: " " Explanation: The input string is "()() ", with primitive decomposition "() " + "() ". After removing outer parentheses of each part, this is " " + " " = " ".
Constraints:
1 <= s.length <= 105s[i] is either '(' or ')'.s is a valid parentheses string.program main
implicit none
character(len=100) :: s
integer :: i
! Examples
s = ""
call remove_outer_parens(s)
write (*,*) trim(s)
s = "()"
call remove_outer_parens(s)
write (*,*) trim(s)
s = "(())()"
call remove_outer_parens(s)
write (*,*) trim(s)
s = "((()))()"
call remove_outer_parens(s)
write (*,*) trim(s)
contains
subroutine remove_outer_parens(s)
implicit none
character(len=*), intent(inout) :: s
integer :: i
do while (s(1:1) == '(' .and. s(len_trim(s):len_trim(s)) == ')')
s = s(2:len_trim(s)-1)
end do
do while (s(1:1) == '(')
i = index(s, '(')
s = s(i+1:)
end do
do while (s(len_trim(s):len_trim(s)) == ')')
s = s(:len_trim(s)-1)
end do
end subroutine remove_outer_parens
end program main))( )))(
module remove_outer_parentheses
implicit none
contains
function remove_outer_parentheses_recursive(s, i, j) result(result)
character(len=*), intent(in) :: s
integer, intent(in) :: i, j
character(len=:), allocatable :: result
if (i > j) then
result = ""
elseif (s(i:i) == "(" .and. s(j:j) == ")") then
result = remove_outer_parentheses_recursive(s, i+1, j-1)
else
result = s(i:j)
endif
end function remove_outer_parentheses_recursive
function remove_outer_parentheses_iterative(s) result(result)
character(len=*), intent(in) :: s
character(len=:), allocatable :: result
integer :: i, j
i = 1
j = len(s)
do while (i <= j)
if (s(i:i) == "(" .and. s(j:j) == ")") then
result = remove_outer_parentheses_recursive(s, i+1, j-1)
exit
endif
i = i + 1
enddo
end function remove_outer_parentheses_iterative
end module remove_outer_parentheses
program test_remove_outer_parentheses
use remove_outer_parentheses
implicit none
character(len=*), parameter :: EXAMPLE_1 = "(()())(()) "
character(len=*), parameter :: EXAMPLE_2 = "(()())(())(()(())) "
character(len=*), parameter :: EXAMPLE_3 = "()() "
character(len=:), allocatable :: result
result = remove_outer_parentheses_iterative(EXAMPLE_1)
write (*,*) "Example 1: ", result
result = remove_outer_parentheses_iterative(EXAMPLE_2)
write (*,*) "Example 2: ", result
result = remove_outer_parentheses_iterative(EXAMPLE_3)
write (*,*) "Example 3: ", result
end program test_remove_outer_parentheses
temp.f95:16:13:
16 | result = remove_outer_parentheses_recursive(s, i+1, j-1)
| 1
Error: Function ‘remove_outer_parentheses_recursive’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:47:5:
47 | use remove_outer_parentheses
| 1
Fatal Error: Cannot open module file ‘remove_outer_parentheses.mod’ for reading at (1): No such file or directory
compilation terminated.
def distributeCoins(root):
def dfs(node):
if not node:
return 0
left, right = dfs(node.left), dfs(node.right)
moves[0] += abs(left) + abs(right)
return node.val + left + right - 1
moves = [0]
dfs(root)
return moves[0]
The algorithm uses DFS (Depth-first search) to traverse the binary tree. We start from the root node and move down to the leaf nodes before returning to the parent nodes. In each step, we calculate the number of moves as the absolute difference between the current node's value and 1, because we want every node to have exactly one coin. The total number of moves required is the sum of these absolute differences.
We use a helper function that takes the current node as its argument and returns its excess coins. In each recursive call, the helper function calls itself for left and right children of the node. The number of moves is then incremented by the absolute values of the returned excess coins from the left and right children.
Finally, we return the total number of moves calculated during the traversal.
int distributeCoins(TreeNode* root, int &moves) {
if (root == nullptr) return 0;
int left = distributeCoins(root->left, moves);
int right = distributeCoins(root->right, moves);
moves += abs(left) + abs(right);
return root->val + left + right - 1;
}
int distributeCoins(TreeNode* root) {
int moves = 0;
distributeCoins(root, moves);
return moves;
}
The algorithm uses DFS (Depth-first search) to traverse the binary tree. We start from the root node and move down to the leaf nodes before returning to the parent nodes. In each step, we calculate the number of moves as the absolute difference between the current node's value and 1, because we want every node to have exactly one coin. The total number of moves required is the sum of these absolute differences.
We use a helper function that takes the current node as its argument and returns its excess coins. In each recursive call, the helper function calls itself for left and right children of the node. The number of moves is then incremented by the absolute values of the returned excess coins from the left and right children.
Finally, we return the total number of moves calculated during the traversal.