1.
Introduction
2.
Problem statement
3.
Approaches
4.
Code
5.
Code
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

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

Malay Gain
0 upvote

Introduction

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

Output

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, and after removing, update the tree representation.
• After removing all the characters in the string, the return value of count.

Code

Output

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).

Check out this problem - Count Inversions

FAQs

1. 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.

2. 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.

3. 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.

Recommended problems -

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.

Happy learning!

Live masterclass