Make The String Great - Leetcode Solution

Problem: Given a string s of lowercase characters, you need to remove all the adjacent duplicates. After removing the adjacent duplicates, return the smallest possible string that could be formed.

Example: Input: s = "leEeetcode" Output: "leetcode" Explanation: In "leEeetcode", 'e' and 'E' are adjacent and duplicate, so we should delete one of them. After deleting 'E', string becomes "leetcode".

Solution: This problem is a classic example of using a stack data structure. We can use a stack to store all the non-duplicate characters. We will push all the characters of the string one by one, and check if the top element of the stack and the current element is same or not. If they are the same, we will pop the top element from the stack, and continue with the next element. If they are not the same, we will push the element to the stack.

Algorithm:

1. Initialize an empty stack.
2. Loop through each character of the string. a. If stack is empty, push the current character to the stack. b. If the current character and the top element of the stack are same, pop the top element from the stack. c. Else, push the current character to the stack.
3. Convert the stack to string and return it.

Code in Python:

def makeGood(s: str) -> str:
    stack = [] # initialize an empty stack
    for char in s:
        if len(stack) == 0:
            stack.append(char)
        elif char == stack[-1].swapcase(): # if the current character and the top element of the stack are same, pop the top element from the stack
            stack.pop()
        else:
            stack.append(char) # else push the current character to the stack
    return ''.join(stack) # convert the stack to string and return it

The time complexity of this algorithm is O(n) as we are looping through each character only once, and the space complexity is also O(n) as we are storing the characters in a stack.

1