Given a string s of lower and upper case English letters.
A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:
0 <= i <= s.length - 2s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.
Return the string after making it good. The answer is guaranteed to be unique under the given constraints.
Notice that an empty string is also good.
Example 1:
Input: s = "leEeetcode " Output: "leetcode " Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode " to be reduced to "leetcode ".
Example 2:
Input: s = "abBAcC " Output: " " Explanation: We have many possible scenarios, and all lead to the same answer. For example: "abBAcC " --> "aAcC " --> "cC " --> " " "abBAcC " --> "abBA " --> "aA " --> " "
Example 3:
Input: s = "s " Output: "s "
Constraints:
1 <= s.length <= 100s contains only lower and upper case English letters.program main
implicit none
character(len=:), allocatable :: s
integer :: i
! Examples
s = 'leEeetcode '
call solve(s)
print *, s
s = 'abBAcC '
call solve(s)
print *, s
s = 's '
call solve(s)
print *, s
contains
subroutine solve(s)
implicit none
character(len=*), intent(inout) :: s
logical :: is_good
do while (.not. is_good(s))
call reduce(s)
end do
end subroutine solve
function is_good(s) result(is_good_)
implicit none
character(len=*), intent(in) :: s
integer :: i
is_good_ = .true.
do i = 1, len(s) - 1
if (is_adjacent(s(i:i+1))) then
is_good_ = .false.
exit
end if
end do
end function is_good
subroutine reduce(s)
implicit none
character(len=*), intent(inout) :: s
integer :: i
do i = 1, len(s) - 1
if (is_adjacent(s(i:i+1))) then
call delete_char(s, i)
return
end if
end do
end subroutine reduce
logical function is_adjacent(s)
implicit none
character(len=2), intent(in) :: s
is_adjacent = (s(1:1) == lcase(s(2:2))) .or. &
(s(1:1) == ucase(s(2:2)))
end function is_adjacent
subroutine delete_char(s, i)
implicit none
character(len=*), intent(inout) :: s
integer, value :: i
s = s(:i-1) // s(i+1:)
end subroutine delete_char
end program maintemp.f95:32:40:
32 | function is_good(s) result(is_good_)
| 1
Error: Function result ‘is_good_’ at (1) has no IMPLICIT type
temp.f95:64:33:
64 | (s(1:1) == ucase(s(2:2)))
| 1
Error: Function ‘ucase’ at (1) has no IMPLICIT type
module good_string
implicit none
contains
function make_good(s) result(res)
character(len=*), intent(in) :: s
character(len=len(s)) :: res
integer :: i, j, n
logical :: found
res = s
n = len(s)
do while (res /= "")
found = .false.
do i = 1, n - 1
if (res(i:i) == res(i+1:i+1)) then
if (res(i:i) >= "a" .and. res(i:i) <= "z" .and. res(i+1:i+1) >= "A" .and. res(i+1:i+1) <= "Z") then
res(i:i+1) = ""
found = .true.
else if (res(i:i) >= "A" .and. res(i:i) <= "Z" .and. res(i+1:i+1) >= "a" .and. res(i+1:i+1) <= "z") then
res(i:i+1) = ""
found = .true.
end if
end if
end do
if (.not. found) exit
end do
end function make_good
end module good_string
program test_good_string
use good_string
implicit none
character(len=100) :: s
character(len=100) :: res
s = "leEeetcode "
res = make_good(s)
write (*,*) res
s = "abBAcC "
res = make_good(s)
write (*,*) res
s = "s "
res = make_good(s)
write (*,*) res
end program test_good_string
leEeetcode abBAcC s
def goodNodes(root, maxVal=float('-inf')):
if not root:
return 0
result = 0
if root.val >= maxVal:
result = 1
maxVal = root.val
return result + goodNodes(root.left, maxVal) + goodNodes(root.right, maxVal)
The algorithm performs a depth-first search on the given binary tree. In order to traverse the tree and count the good nodes, the recursive goodNodes function is called, passing the current node and the maximum value found up to the current node.
result variable to store the number of good nodes.result by 1 and set maxVal to the current node's value.result plus the sum of the good nodes found in both the left and right child subtrees.The base case for the recursion is when the root is null, in which case the function returns 0. This ensures that the function eventually terminates.
When all nodes of the binary tree have been visited, the function returns the total number of good nodes.
int goodNodes(TreeNode* root, int maxVal = INT_MIN) {
if (!root) return 0;
int result = 0;
if (root->val >= maxVal) {
result = 1;
maxVal = root->val;
}
return result + goodNodes(root->left, maxVal) + goodNodes(root->right, maxVal);
}
The algorithm performs a depth-first search on the given binary tree. In order to traverse the tree and count the good nodes, the recursive goodNodes function is called, passing the current node and the maximum value found up to the current node.
result variable to store the number of good nodes.result by 1 and set maxVal to the current node's value.result plus the sum of the good nodes found in both the left and right child subtrees.The base case for the recursion is when the root is null, in which case the function returns 0. This ensures that the function eventually terminates.
When all nodes of the binary tree have been visited, the function returns the total number of good nodes.