Dada una string str , que consta de alfabetos ingleses en minúsculas, la tarea es calcular la suma de índices (indexación basada en 1) de los caracteres eliminados para obtener una string vacía mediante las siguientes operaciones:
- Elimina el alfabeto más pequeño de la string.
- Para múltiples apariciones del alfabeto más pequeño, elimine el presente en el índice más pequeño.
- Después de eliminar cada carácter, los índices de todos los caracteres a su derecha se reducen en 1.
Ejemplos:
Entrada: str = “aba”
Salida: 4
Explicación: “ a ba” -> “ba”, Suma = 1
“b a ” -> “b”, Suma = 1 + 2 = 3
“b” -> “”, Suma = 3 + 1 = 4Entrada: str = «geeksforgeeks»
Salida: 41
Enfoque ingenuo:
siga los pasos a continuación para resolver el problema:
- Encuentre el carácter más pequeño con índice mínimo.
- Elimine ese carácter de la string y cambie todos los caracteres un índice a la derecha.
- Repita los pasos anteriores hasta que la string esté vacía.
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante Segment Tree y Hashing. Siga los pasos a continuación para resolver el problema:
- Se puede observar que solo los índices a la derecha del carácter eliminado se ven afectados, es decir, deben desplazarse una posición.
- Almacena los índices de los personajes en un HashMap
- Procesa los caracteres en el HashMap.
- Encuentre la cantidad de elementos que quedan en el índice actual del carácter, que ya se eliminaron de la string, utilizando Segment Tree.
- Extraiga el índice del carácter eliminado y busque en el rango [0, índice del elemento extraído] en el Árbol de segmentos y encuentre el recuento de índices en el rango presente en el Árbol de segmentos.
- Agregar índice del elemento extraído: cuente hasta la respuesta e inserte el índice del elemento actualmente eliminado en el árbol de segmentos.
- Repita los pasos anteriores hasta que la string esté vacía.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to add index of the deleted character
void 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 index
int 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 Code
int main()
{
string s = "geeksforgeeks";
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 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.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 Code
public static void main(String[] args)
{
String s = "geeksforgeeks";
sumOfIndices(s);
}
}
// This code is contributed by Kingash
Python3
# Python3 program to implement the above approach
import math, collections
# Function to add index of the deleted character
def 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 index
def 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 indices
def 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 = "geeksforgeeks"
sumOfIndices(s)
# This code is contributed by mukesh07.
C#
// C# program to implement
// the above approach
using 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 = "geeksforgeeks";
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 = "geeksforgeeks";
sumOfIndices(s);
// Thiss code is contributed by divyesh072019.
</script>
Producción:
41
Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por godaraji47 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA