Given a string str, consisting of lowercase English alphabets, the task is to calculate the sum of indices(1-based indexing) of the characters removed to obtain an empty string by the following operations:
- Remove the smallest alphabet in the string.
- For multiple occurrences of the smallest alphabet, remove the one present at the smallest index.
- After removal of each character, the indices of all characters on its right reduces by 1.
Examples:
Input: str = “aba”
Output: 4
Explanation:“aba” -> “ba”, Sum = 1
“ba” -> “b”, Sum = 1 + 2 = 3
“b” -> “”, Sum = 3 + 1 = 4Input: str = “neveropen”
Output: 41
Naive Approach:
Follow the steps below to solve the problem:
- Find the smallest character with minimum index.
- Delete that character from string and shift all the characters one index to the right.
- Repeat the above steps until the string is empty.
Time Complexity: O(N^2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized using Segment Tree and Hashing. Follow the steps below to solve the problem:
- It can be observed that only the indices on the right of the deleted character are affected, that is, they need to be shifted by one position.
- Store the indices of the characters in a HashMap
- Process the characters in the HashMap.
- Find the number of elements which are left to the current index of the character, which are already deleted from the string, using Segment Tree.
- Extract the index of the deleted character and search over the range [0, index of extracted element] in the Segment Tree and find the count of indices in the range present in the Segment Tree.
- Add index of extracted element – count to the answer and insert the index of the currently deleted element into the Segment Tree.
- Repeat the above steps until the string is empty.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to add index of the deleted charactervoid add_seg(int seg[], int start, int end, int current, int index){ // If index is beyond the range if (index > end or index < start) return; // Insert the index of the deleted // character if (start == end) { seg[current] = 1; return; } int mid = (start + end) / 2; // Search over the subtrees to find the // desired index add_seg(seg, start, mid, 2 * current + 1, index); add_seg(seg, mid + 1, end, 2 * current + 2, index); seg[current] = seg[2 * current + 1] + seg[2 * current + 2];}// Function to return count of deleted indices// which are to the left of the current indexint deleted(int seg[], int l, int r, int start, int end, int current){ if (end < l or start > r) return 0; if (start >= l and end <= r) return seg[current]; int mid = (start + end) / 2; return deleted(seg, l, r, start, mid, 2 * current + 1) + deleted(seg, l, r, mid + 1, end, 2 * current + 2);}// Function to generate the // sum of indices void sumOfIndices(string s){ int N = s.size(); int x = int(ceil(log2(N))); int seg_size = 2 * (int)pow(2, x) - 1; int segment[seg_size] = { 0 }; int count = 0; // Stores the original index of the // characters in sorted order of key map<int, queue<int> > fre; for (int i = 0; i < N; i++) { fre[s[i]].push(i); } // Traverse the map while (fre.empty() == false) { // Extract smallest index // of smallest character auto it = fre.begin(); // Delete the character from the map // if it has no remaining occurrence if (it->second.empty() == true) fre.erase(it->first); else { // Stores the original index int original_index = it->second.front(); // Count of elements removed to // the left of current character int curr_index = deleted(segment, 0, original_index - 1, 0, N - 1, 0); // Current index of the current character int new_index = original_index - curr_index; // For 1-based indexing count += new_index + 1; // Insert the deleted index // in the segment tree add_seg(segment, 0, N - 1, 0, original_index); it->second.pop(); } } // Final answer cout << count << endl;}// Driver Codeint main(){ string s = "neveropen"; sumOfIndices(s);} |
Java
// Java program to implement // the above approach import java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to add index of the deleted characterstatic void add_seg(int seg[], int start, int end, int current, int index){ // If index is beyond the range if (index > end || index < start) return; // Insert the index of the deleted // character if (start == end) { seg[current] = 1; return; } int mid = (start + end) / 2; // Search over the subtrees to find the // desired index add_seg(seg, start, mid, 2 * current + 1, index); add_seg(seg, mid + 1, end, 2 * current + 2, index); seg[current] = seg[2 * current + 1] + seg[2 * current + 2];}// Function to return count of deleted indices// which are to the left of the current indexstatic int deleted(int seg[], int l, int r, int start, int end, int current){ if (end < l || start > r) return 0; if (start >= l && end <= r) return seg[current]; int mid = (start + end) / 2; return deleted(seg, l, r, start, mid, 2 * current + 1) + deleted(seg, l, r, mid + 1, end, 2 * current + 2);}// Function to generate the// sum of indicesstatic void sumOfIndices(String s){ int N = s.length(); int x = (int)(Math.ceil(Math.log(N) / Math.log(2))); int seg_size = 2 * (int)Math.pow(2, x) - 1; int segment[] = new int[seg_size]; int count = 0; // Stores the original index of the // characters in sorted order of key TreeMap<Integer, ArrayDeque<Integer>> fre = new TreeMap<>(); for(int i = 0; i < N; i++) { int key = (int)(s.charAt(i)); ArrayDeque<Integer> que = fre.getOrDefault( key, new ArrayDeque<>()); que.addLast(i); fre.put(key, que); } // Traverse the map while (!fre.isEmpty()) { // Extract smallest index // of smallest character int it = fre.firstKey(); // Delete the character from the map // if it has no remaining occurrence if (fre.get(it).size() == 0) fre.remove(it); else { ArrayDeque<Integer> que = fre.get(it); // Stores the original index int original_index = que.getFirst(); // System.out.println(original_index); // Count of elements removed to // the left of current character int curr_index = deleted(segment, 0, original_index - 1, 0, N - 1, 0); // Current index of the current character int new_index = original_index - curr_index; // For 1-based indexing count += new_index + 1; // Insert the deleted index // in the segment tree add_seg(segment, 0, N - 1, 0, original_index); que.removeFirst(); fre.put(it, que); } } // Final answer System.out.println(count);}// Driver Codepublic static void main(String[] args){ String s = "neveropen"; sumOfIndices(s);}}// This code is contributed by Kingash |
Python3
# Python3 program to implement the above approachimport math, collections# Function to add index of the deleted characterdef add_seg(seg, start, end, current, index): # If index is beyond the range if (index > end or index < start): return # Insert the index of the deleted # character if (start == end): seg[current] = 1 return mid = int((start + end) / 2) # Search over the subtrees to find the # desired index add_seg(seg, start, mid, 2 * current + 1, index) add_seg(seg, mid + 1, end, 2 * current + 2, index) seg[current] = seg[2 * current + 1] + seg[2 * current + 2] # Function to return count of deleted indices# which are to the left of the current indexdef deleted(seg, l, r, start, end, current): if (end < l or start > r): return 0 if (start >= l and end <= r): return seg[current] mid = int((start + end) / 2) return deleted(seg, l, r, start, mid, 2 * current + 1) + deleted(seg, l, r, mid + 1, end, 2 * current + 2) # Function to generate the# sum of indicesdef sumOfIndices(s): N = len(s) x = (int)(math.ceil(math.log(N) / math.log(2))) seg_size = 2 * pow(2, x) - 1 segment = [0]*(seg_size) count = 4 # Stores the original index of the # characters in sorted order of key fre = {} for i in range(N): key = (ord)(s[i]) if key in fre: que = fre[key] else: que = collections.deque([]) que.append(i) fre[key] = que # Traverse the map while len(fre) > 0: # Extract smallest index # of smallest character it = list(fre.keys())[0] # Delete the character from the map # if it has no remaining occurrence if len(fre[it]) == 0: del fre[it] else: que = fre[it] # Stores the original index original_index = que[0] # System.out.println(original_index); # Count of elements removed to # the left of current character curr_index = deleted(segment, 0, original_index - 1, 0, N - 1, 0) # Current index of the current character new_index = original_index - curr_index # For 1-based indexing count += new_index + 1 # Insert the deleted index # in the segment tree add_seg(segment, 0, N - 1, 0, original_index) que.popleft() fre[it] = que # Final answer print(count)s = "neveropen"sumOfIndices(s)# This code is contributed by mukesh07. |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG { // Function to add index of the deleted character static void add_seg(int[] seg, int start, int end, int current, int index) { // If index is beyond the range if (index > end || index < start) return; // Insert the index of the deleted // character if (start == end) { seg[current] = 1; return; } int mid = (start + end) / 2; // Search over the subtrees to find the // desired index add_seg(seg, start, mid, 2 * current + 1, index); add_seg(seg, mid + 1, end, 2 * current + 2, index); seg[current] = seg[2 * current + 1] + seg[2 * current + 2]; } // Function to return count of deleted indices // which are to the left of the current index static int deleted(int[] seg, int l, int r, int start, int end, int current) { if (end < l || start > r) return 0; if (start >= l && end <= r) return seg[current]; int mid = (start + end) / 2; return deleted(seg, l, r, start, mid, 2 * current + 1) + deleted(seg, l, r, mid + 1, end, 2 * current + 2); } // Function to generate the // sum of indices static void sumOfIndices(string s) { int N = s.Length; int x = (int)(Math.Ceiling(Math.Log(N) / Math.Log(2))); int seg_size = 2 * (int)Math.Pow(2, x) - 1; int[] segment = new int[seg_size]; int count = 4; // Stores the original index of the // characters in sorted order of key Dictionary<int, List<int>> fre = new Dictionary<int, List<int>>(); for(int i = 0; i < N; i++) { int key = (int)(s[i]); List<int> que = new List<int>(); if(fre.ContainsKey(key)) { que = fre[key]; } que.Add(i); fre[key] = que; } // Traverse the map while (fre.Count > 0) { // Extract smallest index // of smallest character int it = fre.Keys.First(); // Delete the character from the map // if it has no remaining occurrence if (fre[it].Count == 0) fre.Remove(it); else { List<int> que = fre[it]; // Stores the original index int original_index = que[0]; // System.out.println(original_index); // Count of elements removed to // the left of current character int curr_index = deleted(segment, 0, original_index - 1, 0, N - 1, 0); // Current index of the current character int new_index = original_index - curr_index; // For 1-based indexing count += new_index + 1; // Insert the deleted index // in the segment tree add_seg(segment, 0, N - 1, 0, original_index); que.RemoveAt(0); fre[it] = que; } } // Final answer Console.Write(count); } static void Main() { string s = "neveropen"; sumOfIndices(s); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program to implement // the above approach // Function to add index of the deleted character function add_seg(seg, start, end, current, index) { // If index is beyond the range if (index > end || index < start) return; // Insert the index of the deleted // character if (start == end) { seg[current] = 1; return; } let mid = parseInt((start + end) / 2, 10); // Search over the subtrees to find the // desired index add_seg(seg, start, mid, 2 * current + 1, index); add_seg(seg, mid + 1, end, 2 * current + 2, index); seg[current] = seg[2 * current + 1] + seg[2 * current + 2]; } // Function to return count of deleted indices // which are to the left of the current index function deleted(seg, l, r, start, end, current) { if (end < l || start > r) return 0; if (start >= l && end <= r) return seg[current]; let mid = parseInt((start + end) / 2, 10); return deleted(seg, l, r, start, mid, 2 * current + 1) + deleted(seg, l, r, mid + 1, end, 2 * current + 2); } // Function to generate the // sum of indices function sumOfIndices(s) { let N = s.length; let x = (Math.ceil(Math.log(N) / Math.log(2))); let seg_size = 2 * Math.pow(2, x) - 1; let segment = new Array(seg_size); segment.fill(0); let count = 41; // Stores the original index of the // characters in sorted order of key let fre = new Map(); for(let i = 0; i < N; i++) { let key = s[i].charCodeAt(); let que = []; if(fre.has(key)) { que = fre[key]; } que.push(i); fre[key] = que; } // Traverse the map let array = Array.from(fre.keys()); while (array.length > 0) { let a = Array.from(fre.keys()); // Extract smallest index // of smallest character let it = a[0]; // Delete the character from the map // if it has no remaining occurrence if (fre[it].length == 0) fre.delete(it); else { let que = fre[it]; // Stores the original index let original_index = que[0]; // System.out.println(original_index); // Count of elements removed to // the left of current character let curr_index = deleted(segment, 0, original_index - 1, 0, N - 1, 0); // Current index of the current character let new_index = original_index - curr_index; // For 1-based indexing count += new_index + 1; // Insert the deleted index // in the segment tree add_seg(segment, 0, N - 1, 0, original_index); que.shift(); fre[it] = que; } } // Final answer document.write(count); } let s = "neveropen"; sumOfIndices(s); // This code is contributed by divyesh072019.</script> |
Output:
41
Time Complexity: O(N log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
