A string is nothing but an array of characters. Previously we have discussed many strings related problems as well as algorithms. In this article, we will discuss an advanced problem on string operation. First, we will understand the problem statement, and then different solution approaches will be discussed. We will also analyze the complexity of each approach after corresponding C++ implementation.

Problem statement

You are given a string. You need to perform n operations on the string where n is equal to the length of the string.

In each operation, you need to remove the alphabetically smallest character from the string and considering 1-base indexing add the index of the character with the count. Initially, the value of the count is 0.

If multiple same characters are present in the string, remove the character having the smallest index.

Write a program to find the value of count after n operations.

Input

n=5, str="abacb"

Output

count=7

Note: Please try to solve the problem first and then see the below solution approach.

Approaches

Brute force approach

Before performing each removal operation, we will traverse the string to find the alphabetically smallest character and its index from the remaining string.

After finding its index, we will perform removal operation and add index value with count

We will repeat the above steps until it becomes an empty string (i.e. n times)

Code

#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);
}

Output

Value of count after n removal operations : 7

Complexity analysis

The above approach takes O(n2) time where n is the length of the given string.

As no extra space is used, the space complexity is O(1).

Optimized approach using Binary indexed tree

This problem can be solved efffciently using Fenwick tree or binary indexed tree.

Follow the below steps one by one

Create a Fenwick tree from the indices of characters to efficiently find the number of characters present before any given index. We will use a class to define the Fenwick tree.

Store the values of indices of all the characters of the given string in increasing order.

Then start removing the character in alphabetically increasing order, i.e., removing a character from the string means its corresponding value in the array is changed to 0, indicating that it is removed.

Before removing, find the character's position in the string using the Fenwick Tree and add the position value to the count, andafter removing, update the tree representation.

After removing all the characters in the string, the return value of count.

//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);
}

Output

Value of count after n removal operations : 7

Complexity analysis

The above approach takes O(nlogn) time where n is the length of the given string.

As extra space is used for creating Fenwick tree, the space complexity is O(n).

What is the binary indexed tree? Binary Indexed Tree or Fenwick Tree is a special kind of data structure to calculate the sum of a given range of an array and update the array efficiently for a large number of queries.

Difference between binary indexed tree and segment tree? The binary indexed tree takes less space than the segment tree, and its implementation is relatively easier than a segment tree.

Application of binary indexed tree? Binary indexed tree is used to count inversions in an array and to implement arithmetic coding algorithms.

Key Takeaways

This article covered how to create a linked list from a given array. A good grasp of Linked Lists can be a huge plus point in a coding interview.

Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.