Given a string str, the task is to remove all the continuous occurrences of a and all occurrences of b and print the resultant string.
Examples
Input: str = “abcddabcddddabbbaaaaaa”
Output: acddacdddda
‘abcddabcddddabbbaaaaaa’ will not result in ‘acddacddddaa’ because after removing the required occurrences, the string will become ‘acddacddddaa’ which will result in ‘acddacdddda’Input: str = “aacbccdbsssaba”
Output: acccdsssa
Approach: We initialize an empty result string. We traverse the input string if the current character is b or current character is a and last character of result string is also a then ignore the character else push the character into the result string.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to get the resultant string after// removing the required occurrencesstring removeOccurrences(string str){ // String to store the resultant string string res = ""; for (int i = 0; i < str.size(); i++) { // If 'a' appeared more than once continuously if (str[i] == 'a' && res.back() == 'a') // Ignore the character continue; // Ignore all 'b' characters else if (str[i] == 'b') continue; // Characters that will be included // in the resultant string res = res + str[i]; } return res;}// Driver codeint main(){ string str = "abcddabcddddabbbaaaaaa"; cout << removeOccurrences(str); return 0;} |
Java
//Java implementation of the approach class solution{// Function to get the resultant String after // removing the required occurrences static String removeOccurrences(String str) { // String to store the resultant String String res = ""; for (int i = 0; i < str.length(); i++) { // If 'a' appeared more than once continuously if (str.charAt(i) == 'a' && (res.length()==0?' ':res.charAt(res.length()-1)) == 'a') // Ignore the character continue; // Ignore all 'b' characters else if (str.charAt(i) == 'b') continue; // Characters that will be included // in the resultant String res = res + str.charAt(i); } return res; } // Driver code public static void main(String args[]) { String str = "abcddabcddddabbbaaaaaa"; System.out.println(removeOccurrences(str));} }//contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach # Function to get the resultant string # after removing the required occurrences def removeOccurrences(str) : # String to store the resultant string res = "" for i in range(len(str)) : # If 'a' appeared more than # once continuously if (res) : if (str[i] == 'a' and res[-1] == 'a') : # Ignore the character continue # Ignore all 'b' characters elif (str[i] == 'b') : continue else : # Characters that will be included # in the resultant string res += str[i] else : if (str[i] == 'a' ) : res += str[i] # Ignore all 'b' characters elif (str[i] == 'b') : continue else : # Characters that will be included # in the resultant string res += str[i] return res# Driver code if __name__ == "__main__" : str = "abcddabcddddabbbaaaaaa" print(removeOccurrences(str)) # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System;class GFG{ // Function to get the resultant String after // removing the required occurrences static String removeOccurrences(String str) { // String to store the resultant String String res = ""; for (int i = 0; i < str.Length; i++) { // If 'a' appeared more than once continuously if (str[i] == 'a' && (res.Length==0?' ': res[res.Length-1]) == 'a') // Ignore the character continue; // Ignore all 'b' characters else if (str[i] == 'b') continue; // Characters that will be included // in the resultant String res = res + str[i]; } return res; } // Driver code public static void Main(String []args) { String str = "abcddabcddddabbbaaaaaa"; Console.WriteLine(removeOccurrences(str));} } // This code has been contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach // Function to get the resultant String after // removing the required occurrences function removeOccurrences(str) { // String to store the resultant String var res = ""; for (var i = 0; i < str.length; i++) { // If 'a' appeared more than once continuously if (str.charAt(i) == 'a' && (res.length==0?' ':res.charAt(res.length-1)) == 'a') // Ignore the character continue; // Ignore all 'b' characters else if (str.charAt(i) == 'b') continue; // Characters that will be included // in the resultant String res = res + str.charAt(i); } return res; } // Driver code var str = "abcddabcddddabbbaaaaaa"; document.write(removeOccurrences(str));// This code contributed by Princi Singh </script> |
Output
acddacdddda
Time complexity: O(n), where n is the length of the input string. This is because the code iterates over each character of the string only once, performing constant time operations for each character.
Auxiliary Space: O(m), where m is the number of characters in the output string. This is because the code uses a single string to store the result, and the size of the result string is proportional to the number of characters that are not removed from the input string.
Another approach:
The idea is to push each character onto the stack while checking if the current character is equal to ‘a’ or ‘b’ and if the last character on the stack is also ‘a’. If so, we pop the ‘a’ from the stack before pushing the current character. If the current character is ‘b’, we simply skip pushing it onto the stack. Finally, we pop all the characters from the stack and append them to the result string.
Implementation of the above approach.
C++
#include <bits/stdc++.h>using namespace std;string removeOccurrences(string str) { stack<char> s; string res; for (char c : str) { if (c == 'b') { continue; } else if (c == 'a' && !s.empty() && s.top() == 'a') { s.pop(); } else { s.push(c); } } while (!s.empty()) { res = s.top() + res; s.pop(); } return res;}int main() { string str = "abcddabcddddabbbaaaaaa"; cout << removeOccurrences(str) << endl; // Output: acddacdddda return 0;} |
Java
// Java program for the above approachimport java.util.*;class Main { static String removeOccurrences(String str) { Stack<Character> s = new Stack<Character>(); String res = ""; for (char c : str.toCharArray()) { if (c == 'b') { continue; } else if (c == 'a' && !s.empty() && s.peek() == 'a') { s.pop(); } else { s.push(c); } } while (!s.empty()) { res = s.peek() + res; s.pop(); } return res; } public static void main(String[] args) { String str = "abcddabcddddabbbaaaaaa"; System.out.println(removeOccurrences(str)); // Output: acddacdddda }}// Contributed by adityasharmadev01 |
Python3
def removeOccurrences(s: str) -> str: stack = [] res = '' for c in s: if c == 'b': continue elif c == 'a' and stack and stack[-1] == 'a': stack.pop() else: stack.append(c) while stack: res = stack.pop() + res return resstr = "abcddabcddddabbbaaaaaa"print(removeOccurrences(str)) # Output: acddacdddda |
C#
using System;using System.Collections.Generic;class Program { static string RemoveOccurrences(string str) { Stack<char> s = new Stack<char>(); string res = ""; foreach(char c in str) { if (c == 'b') { continue; } else if (c == 'a' && s.Count > 0 && s.Peek() == 'a') { s.Pop(); } else { s.Push(c); } } while (s.Count > 0) { res = s.Peek() + res; s.Pop(); } return res; } static void Main(string[] args) { string str = "abcddabcddddabbbaaaaaa"; Console.WriteLine(RemoveOccurrences(str)); // Output: acddacdddda }}// This code is contributed by Prajwal Kandekar |
Javascript
function removeOccurrences(str) { let s = []; let res = ""; for (let i = 0; i < str.length; i++) { let c = str[i]; if (c === 'b') { continue; } else if (c === 'a' && s.length > 0 && s[s.length - 1] === 'a') { s.pop(); } else { s.push(c); } } while (s.length > 0) { res = s[s.length - 1] + res; s.pop(); } return res;}let str = "abcddabcddddabbbaaaaaa";console.log(removeOccurrences(str)); // Output: acddacdddda |
Output
acddacdddda
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach Name: Using Two Pointers and String Concatenation
Steps:
- Initialize an empty string called result.
- Initialize two pointers i and j to 0.
- Iterate over the string from the first character to the second to last character:
a. If the current character is ‘a’ and the next character is not ‘a’, append the current character to result.
b. If the current character is not ‘a’, append the current character to result. - If the last character is not ‘a’, append the last character to result.
- Replace all occurrences of ‘b’ in the result string with an empty string.
- Print the resulting string.
C++
#include <iostream>#include <string>#include <algorithm>std::string remove_continuous_a_and_b(std::string str) { std::string result = ""; int i = 0; while (i < str.length() - 1) { if (str[i] == 'a' && str[i+1] != 'a') { result += str[i]; } else if (str[i] != 'a') { result += str[i]; } i++; } if (str[str.length() - 1] != 'a') { result += str[str.length() - 1]; } result.erase(std::remove(result.begin(), result.end(), 'b'), result.end()); return result;}int main() { std::string input_str = "abcddabcddddabbbaaaaaa"; std::string result_str = remove_continuous_a_and_b(input_str); std::cout << result_str << std::endl; return 0;} |
Java
import java.io.*;import java.util.*;public class Main { public static String removeContinuousAAndB(String str) { String result = ""; int i = 0; while (i < str.length() - 1) { if (str.charAt(i) == 'a' && str.charAt(i + 1) != 'a') { result += str.charAt(i); } else if (str.charAt(i) != 'a') { result += str.charAt(i); } i++; } if (str.charAt(str.length() - 1) != 'a') { result += str.charAt(str.length() - 1); } result = result.replace("b", ""); return result; } public static void main(String[] args) { String inputStr = "abcddabcddddabbbaaaaaa"; String resultStr = removeContinuousAAndB(inputStr); System.out.println(resultStr); }} |
Python3
def remove_continuous_a_and_b(str): result = "" i = 0 while i < len(str) - 1: if str[i] == 'a' and str[i+1] != 'a': result += str[i] elif str[i] != 'a': result += str[i] i += 1 if str[-1] != 'a': result += str[-1] result = result.replace('b', '') return result# Example Usageinput_str = "abcddabcddddabbbaaaaaa"result_str = remove_continuous_a_and_b(input_str)print(result_str) |
C#
using System;class Program{ static string RemoveContinuousAAndB(string str) { string result = ""; int i = 0; while (i < str.Length - 1) { if (str[i] == 'a' && str[i + 1] != 'a') { result += str[i]; } else if (str[i] != 'a') { result += str[i]; } i++; } if (str[str.Length - 1] != 'a') { result += str[str.Length - 1]; } result = result.Replace("b", ""); return result; } static void Main() { string input_str = "abcddabcddddabbbaaaaaa"; string result_str = RemoveContinuousAAndB(input_str); Console.WriteLine(result_str); }} |
Javascript
// Function to remove continuous 'a' and 'b' characters from a given stringfunction removeContinuousAandB(str) { let result = ""; let i = 0; // Iterate through the string, checking each character and its adjacent character while (i < str.length - 1) { // If the current character is 'a' and the next one is not 'a', add it to the result if (str[i] === 'a' && str[i + 1] !== 'a') { result += str[i]; } // If the current character is not 'a', add it to the result else if (str[i] !== 'a') { result += str[i]; } i++; } // Add the last character to the result if it's not 'a' if (str[str.length - 1] !== 'a') { result += str[str.length - 1]; } // Remove all occurrences of 'b' from the result using the 'replace' method result = result.replace(/b/g, ''); return result;}// Test the function with an example input stringconst inputStr = "abcddabcddddabbbaaaaaa";const resultStr = removeContinuousAandB(inputStr);console.log(resultStr); // Output: "acddacdddaaaaa" |
Output
acddacdddda
Time Complexity: O(n) where n is the length of the input string. We iterate over the string once to create the resulting string and then perform a replace operation on it which takes linear time.
Auxiliary Space: O(n) where n is the length of the input string
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
