Replace All Occurrences of String 'ab' with 'c' in C++

In this article, we will replace "AB" with "C" in the given string having upper case latin characters. The occurrences of "AB" becomes "C," but single "A" and "B" are unaffected.

Let us look at some input scenarios ?

Let's have a string "ABOUTME"

Input: "ABOUTME"
Result: COUTME

We start traversing the string from index one. We then check the current and previous elements for "B" and "A," respectively. If we find it, then we replace the last append ("A") with a "C."

The worst case time complexity will occur when there is no substring "AB" present in the input string. For example, consider a string "cloud"

Input: "CLOUD"
Result: CLOUD

The entire string is traversed with no ?AB' substring present.

Let us also look at the input string with the characters ?A' and ?B' present in it but no consecutively.

Input: "ALIBI"
Result: ALIBI

The output string remains untouched as the substring AB is not present in the input string consecutively.

Algorithm

• Any string is taken as an input and is traversed.

• Each element in the string is compared with the characters of the substring ?AB', i.e., ?A' and ?B'.

• If a match is found, size of the string is decreased by 1 and replaces ?AB' with ?C'.

• The resultant string is obtained as the output with the replaced letters.

Example

For example, let us take a string = "TUTORIALSABPOINT", a C++ program is implemented to check the string for "AB" and replace it with the character "C" ?

#include <iostream>
using namespace std;
string solve(string s) {
   if(s.size() == 0) return s;
   string ans = "";
   ans+=s[0];
   for(int i=1;i<s.size();i++) {
      if(s[i] == 'B' && s[i-1] == 'A') {
         ans[ans.size()-1] = 'C';
      }
      else {
         ans+=s[i];
      }
   }
   return ans;
}
int main() {
   string s = "TUTORIALSABPOINT";
   cout << solve(s) << endl;
   return 0;
}

Output

TUTORIALSCPOINT

Example

Another approach to solving this problem would be to use two indexes. We would use one index to keep track of the original string, and one index would be used to keep track of the modified string. When we encounter "AB" at index j(say for the original string), we increment j by 2 and i(say for the modified string) by 1. If not, we increment each by copying and copying characters.

#include <iostream>
using namespace std;
string solve(string s) {
   int i = 0;
   int j = 0;
   int terminatingIndex = s.size();
   while (j<s.size()-1) {
      if (s[j] == 'A' && s[j+1] == 'B') {
         j = j + 2;
         s[i++] = 'C';
         continue;
      }
      s[i++] = s[j++];
   }
   if (j==s.size()-1) {
      s[i++] = s[j];
   }
   terminatingIndex = i;
   return s.substr(0, terminatingIndex);
}
int main() {
   string s= "ARTICLESABPOINT";
   cout << solve(s);
   return 0;
}

Output

ARTICLESCPOINT

Conclusion

Just traversing the string from index 1 is all for us to compute our new string and check the string for "AB." We created an ans string to get our unique string, but we have not used any extra space apart from that.