1. Remove All Adjacent Duplicates In String

Problem Statement

Given a string s consisting of lowercase English letters, repeatedly remove adjacent duplicate characters until no such duplicates remain. Return the final string.

Pattern Used

Stack (String used as Stack)

Approach (High-level)

• Traverse the string character by character
• Use a result string as a stack
• If current character matches the stack’s top, remove the top
• Otherwise, push the current character

Time & Space Complexity

• Time: O(n)
• Space: O(n)

LeetCode

• 1047. Remove All Adjacent Duplicates In String
• https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

class Solution {
public:
    string removeDuplicates(string s) {
        //intialise ans string as empty string
        string ans = "";        
        int n = s.length();

        for(int i=0; i<n; i++) {
            char currCharacter = s[i];
            if(ans.empty() || currCharacter != ans.back()) {
                //if ans is empty, seedha push karo
                ans.push_back(currCharacter);
            }//rightmost character of ans = ans.back()
            else if(currCharacter == ans.back()) {
                ans.pop_back();
            }
        }
        return ans;
    }
};

2. Remove All Occurrences of a Substring

Problem Statement

Given two strings s and part, repeatedly remove the leftmost occurrence of the substring part from s until no such occurrence exists. Return the final string.