Remove All Adjacent Duplicates In String

🏠 ⬅️ ➡️

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Example 1:

Input: s = "abbaca " Output: "ca " Explanation: For example, in "abbaca " we could remove "bb " since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca ", of which only "aa " is possible, so the final string is "ca ".

Example 2:

Input: s = "azxxzy " Output: "ay "

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    character(len=:), allocatable :: s
    integer :: i, j, n

    ! Example 1
    s = 'abbaca'
    call solve(s)
    print *, s

    ! Example 2
    s = 'azxxzy'
    call solve(s)
    print *, s

contains

subroutine solve(s)
    implicit none
    character(len=*), intent(inout) :: s
    logical :: done

    do while (.not. done)
        done = .true.
        do i = 1, len_trim(s)-1
            if (s(i:i+1) == s(i+1:i+2)) then
                s = s(:i-1) // s(i+2:)
                done = .false.
                exit
            end if
        end do
    end do
end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module main

implicit none

interface

    function remove_duplicates(s) result(res)
        implicit none
        character(len=*), intent(in) :: s
        character(len=len(s)) :: res
    end function remove_duplicates

end interface

character(len=100000) :: s
character(len=100000) :: res

s = "abbaca "
res = remove_duplicates(s)
write (*,*) res

s = "azxxzy "
res = remove_duplicates(s)
write (*,*) res

contains

function remove_duplicates(s) result(res)
    implicit none
    character(len=*), intent(in) :: s
    character(len=len(s)) :: res
    integer :: i, j

    res = s

    do while (any(res(2:len(res)) == res(1:len(res)-1)))
        do i = 1, len(res) - 1
            if (res(i) == res(i+1)) then
                res(i:i+1) = ""
                exit
            end if
        end do
    end do

end function remove_duplicates

end module main
🌐 Data from online sources 
import heapq

def maxSumAfterKOperations(nums, k):
    heapq.heapify(nums)
    for _ in range(k):
        current = heapq.heappop(nums)
        heapq.heappush(nums, -current)
    return sum(nums)
  1. Create a min-heap from the given integer array nums.
  2. Iterate k times and for each iteration, do the following:
  3. Pop the smallest element from the min-heap.
  4. Negate the popped element and push it back to the min-heap.
  5. Calculate the sum of the elements in the min-heap and return it.

Note: In JavaScript, we have also created a PriorityQueue class to achieve the functionality of a priority queue like in other languages.

🌐 Data from online sources 
int maxSumAfterKOperations(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.end());
    while(k--){
        int current = pq.top();
        pq.pop();
        pq.push(-current);
    }
    return accumulate(nums.begin(), nums.end(), 0);
}
  1. Create a min-heap from the given integer array nums.
  2. Iterate k times and for each iteration, do the following:
  3. Pop the smallest element from the min-heap.
  4. Negate the popped element and push it back to the min-heap.
  5. Calculate the sum of the elements in the min-heap and return it.

Note: In JavaScript, we have also created a PriorityQueue class to achieve the functionality of a priority queue like in other languages.