aboutsummaryrefslogtreecommitdiff
path: root/remove_substring.cpp
blob: f3744ab2900b87e15d975e0888110c3f481398c6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 1910. Remove All Occurrences of a Substring
#include "leetcode.h"

/*
 * given two strings 's' and 'part', perform the following operation on 's'
 * until all occurrences of the substring 'part' are removed; find the leftmost
 * occurrence of the substring 'part' and remove it from 's'. return 's' after
 * removing all occurrences of 'part'. a substring is a contiguous sequence of
 * characters in a string
 */

class Solution {
  bool check(stack<char> stk, string part) {
    int n = part.size(), j = n - 1;
    while (j >= 0 && stk.top() == part[j])
      stk.pop(), j--;
    return j == -1;
  }

public:
  string removeOccurrences(string s, string part) {
    int n1 = s.size(), n2 = part.size();
    stack<char> stk;
    string str = "";
    for (int i = 0; i < n1; i++) {
      stk.push(s[i]);
      if (stk.size() >= n2)
        if (check(stk, part)) {
          int cnt = n2;
          while (cnt--)
            stk.pop();
        }
    }
    string ans = "";
    while (!stk.empty()) {
      ans += stk.top();
      stk.pop();
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

int main() {
  Solution obj;
  cout << obj.removeOccurrences("daabcbaabcbc", "abc") << endl; // expect: dab
  cout << obj.removeOccurrences("axxxxyyyyb", "xy") << endl;    // expect: ab
}