#include <iostream>
#include <string>
#include <vector>
using namespace std;

template<typename It, class Pr>
It remove_neighbors(It first, It last, int nSpan, Pr Pred) {
  if (first == last || nSpan <= 0) return last;

  It lastGood = first;
  It cur = first;
  ++cur;
  for (; cur != last; ++cur) {
    bool found = false;
    It back = lastGood;
    for (int i = nSpan; i > 0; --i, --back) {
      if (Pred(*back, *cur)) {
        found = true;
        lastGood = back;
        break;
      }
      if (back == first) break;
    }

    if (!found) {
      ++lastGood;
      *lastGood = std::move(*cur);
    }
  }
  ++lastGood;
  return lastGood;
}

void test_remove_neighbors(const string& in, int nSpan) {
  vector<char> v(in.begin(), in.end());
  vector<char>::iterator trash =
      remove_neighbors(v.begin(), v.end(), nSpan, equal_to<char>());
  string out(v.begin(), trash);
  cout << "In: " << in << " span: " << nSpan << " out: " << out << endl;
}

int main(int argc, char *argv[])
{
  // No ops:
  test_remove_neighbors("abab", 1);
  test_remove_neighbors("abcabc", 2);
  // unique
  test_remove_neighbors("aabbaaabbb", 1);
  // simple
  test_remove_neighbors("abadedf", 2);
  // backtracking
  test_remove_neighbors("abcba", 2);
  return 0;
}