Find Value After N Operations to Remove N Characters of String S with Given Constraints

#include<bits/stdc++.h>
using namespace std;

//function to find the value of count after n removal operation in the given string
 int removal(string s,int n)
 {
 
  int count=0; //initial value of count
 
  while(n>0)
  {
  char c=s[0];
  
  int idx=0;
  
  //finding the alphabetically smallest character and its index from the remaining string
  for(int i=1;i<s.length();i++)
  {
  if(s[i]<c)
  {
  c=s[i];
  idx=i;
}
}

//removing the alphabetically smallest character
s.erase(s.begin()+idx);
count+=idx+1; //adding the index in terms of 1 base indexing 

n--;
}

return count;
 }

//driver code

int main()
{
int n=5;

string str="abacb";

cout<<"Value of count after n removal operations : "<<removal(str,n);
}

//C++ implementation of the above approach

#include<bits/stdc++.h>
using namespace std;

//Binary indexed tree or Fenwick tree

class FenwickTree {

public:

vector<int> BIT;

int n;

//constructor
FenwickTree(int size)
{
n=size+1;
BIT=vector<int>(n,0);

}

void creat(int sz)
{
BIT.clear();
n = sz + 1;
BIT.resize(n + 1, 0);

// Initially mark all
// are present (i.e. 1)
for (int i = 0; i < n; i++)
add(i, 1);
}


//function to add a value to an index
void add(int idx, int val)
{

// Val is nothing but "DELTA"
// index in BITree[] is 1
// more than the index in arr[]
idx = idx + 1;

// Traverse all ancestors
// and add 'val'
while (idx <= n) {

// Add 'val' to current
// node of BI Tree
BIT[idx] += val;

// Update index to that
// of parent in update View
idx += idx & (-idx);
}
}

//prefix sum for an index
int sum(int idx)
{
int ret = 0;

// Index in BITree[] is 1 more
// than the index in arr[]
idx = idx + 1;

// Traverse the ancestors of
// BITree[index]
while (idx > 0) {

// Add current element
// of BITree to sum
ret += BIT[idx];

// Move index to parent
// node in getSum View
idx -= idx & (-idx);
}

// Return the result
return ret;
}


//finding sum for a range[l,r] using prefix sum
int sum(int l, int r)
{
return sum(r) - sum(l - 1);
}

//value at any index
int valAT(int i)
{
sum(i,i);
}
//for updating value at some index
void update(int idx,int val)
{
add(idx, val - valAT(idx));
}


};

//function to find the value of count after n removal operation in the given stiring
int countOfremoval(string s, int n)
{
int  count = 0;

// for each alphabet, we need to store their indexes in the string

vector<vector<int> > mp(26,vector<int>());

// creating fenwick tree
FenwickTree ft = FenwickTree(n);
ft.creat(n);



    int i=0;
for (char ch : s) {

// storing the indexes for each character
mp[ch - 'a'].push_back(i);
i++;
}

    //checking for each character alphabetically
for (i = 0; i < 26; i++) {

// removing the current character in increasing order
//of its indexes
for (int ind : mp[i]) {

// using ft.sum(ind) for finding the number of characters
// currently present before ind position
count += ft.sum(ind);

//updating the Fenwick tree representation after
//removal of current character
ft.update(ind, 0);
}
}

return count;
}
//driver code

int main()
{
int n=5;

string str="abacb";

cout<<"Value of count after n removal operations : "<<countOfremoval(str,n);
}