Remove All Adjacent Duplicates In String
Asked 1 year ago
0Comments
3 Views
Given a string, remove all adjacent duplicate characters recursively. For example, "abbaca" should become "ca" after removing all adjacent duplicates.
Explanation:
- We create an empty string
answerto store our result. - We iterate through each character of the input string
s. - For each character, we check:
- If
answeris not empty and the last character ofansweris the same as the current character ofs, we remove the last character fromanswer(removing the adjacent duplicate). - Otherwise, we add the current character to
answer.
- If
- We return the final
answerstring.
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).
Share