No result illustrationNo result illustration

DevLoom

search

Lets Connect

chevron right
Menu
Home

Home

Community

Community

Blog Posts

Blog Posts

Programming

Programming

Tech Topics

Tech Topics

Explore

Explore

Find Jobs

Find Jobs

Tags

Tags

DevLoomPerfect Place for devs
    profile

    Jubair

    upvoteupvote

    0

    downvote

    0

    star

    Remove All Adjacent Duplicates In String

    clock icon

    Asked 11 months ago

    message

    0Comments

    eye

    3 Views

    Given a string, remove all adjacent duplicate characters recursively. For example, "abbaca" should become "ca" after removing all adjacent duplicates.

    Explanation:

    1. We create an empty string answer to store our result.
    2. We iterate through each character of the input string s.
    3. For each character, we check:
      • If answer is not empty and the last character of answer is the same as the current character of s, we remove the last character from answer (removing the adjacent duplicate).
      • Otherwise, we add the current character to answer.
    4. We return the final answer string.
    class Solution {
    public:
        string removeDuplicates(string s) {
            string answer = "";  // Initialize an empty string to store the result
            int i = 0;  // Initialize index for traversing the input string
    
            // Traverse through each character of the input string
            while (i < s.length()) {
                // Case 1: If answer is empty, simply add the current character
                if (answer.empty()) {
                    answer.push_back(s[i]);
                }
                // Case 2: If answer is not empty, we need to check for duplicates
                else {
                    // If the current character matches the last character in answer,
                    // we've found a duplicate, so remove the last character from answer
                    if (answer.back() == s[i]) {
                        answer.pop_back();
                    }
                    // If it's not a duplicate, add the current character to answer
                    else {
                        answer.push_back(s[i]);
                    }
                }
                
                i++;  // Move to the next character in the input string
            }
    
            // Return the final string with all adjacent duplicates removed
            return answer;
        }
    };

    Test Case 1: Input: s = "abbaca" Process:

    • i=0: answer = "a"
    • i=1: answer = "ab"
    • i=2: answer = "a" (removed 'b')
    • i=3: answer = "" (removed 'a')
    • i=4: answer = "c"
    • i=5: answer = "ca" Output: "ca"

    COOL !

    But ! This is How Beginners Write Code ! But Some Better way to Write code !

    string removeDuplicates(string s) {
        string answer = "";  // Initialize an empty string to store the result
        
        int i = 0;
        
        while (i < s.length()) {
            // If answer is empty or the current character is different from the last character in answer
            if (answer.empty() || answer.back() != s[i]) {
                answer.push_back(s[i]);
            }
            // If the current character is the same as the last character in answer
            else {
                answer.pop_back();
            }
            i++;
        }
        
        return answer;
    }

    and One more Way to Write the Same Code!

    class Solution {
    public:
        string removeDuplicates(string s) {
            string answer = "";  // Initialize an empty string to store the result
            
            // Traverse through each character of the input string
            for (char c : s) {
                // If answer is not empty and the current character matches 
                // the last character inanswer,
                // we've found a duplicate, so remove the last character from answer
                if (!answer.empty() && answer.back() == c) {
                    answer.pop_back();
                }
                // Otherwise, add the current character to answer
                else {
                    answer.push_back(c);
                }
            }
    
            // Return the final string with all adjacent duplicates removed
            return answer;
        }
    };
    

    It maintains the time complexity of O(n) where n is the length of the input string, and uses O(n) space in the worst case (when no duplicates are removed).

    Duplicates
    Strings
    LeetCode
    medium

    Share

    Write your comment here !

    0 Responses