Dada una string S de tamaño N. Inicialmente, el valor de count es 0 . La tarea es encontrar el valor de count después de N operaciones para eliminar todos los N caracteres de la string S dada, donde cada operación es:
- En cada operación, seleccione alfabéticamente el carácter más pequeño de la string S y elimine ese carácter de S y agregue su índice para contar.
- Si hay varios caracteres presentes, elimine el carácter que tenga el índice más pequeño.
Nota: Considere la string como una indexación basada en 1.
Ejemplos:
Entrada: N = 5, S = «abcab»
Salida: 8
Explicación:
elimine el carácter ‘a’, la string se convierte en «bcab» y la cuenta = 1.
Elimine el carácter ‘a’, la string se convierte en «bcb» y la cuenta = 1 + 3 = 4.
Elimine el carácter ‘b’, luego la string se convierte en «cb» y el conteo = 4 + 1 = 5.
Elimine el carácter ‘b’, luego la string se convierte en «c» y el conteo = 5 + 2 = 7.
Elimine el carácter ‘c ‘ entonces la string se convierte en «» y la cuenta = 7 + 1 = 8.Entrada: N = 5 S = “aabbc”
Salida: 5
Explicación:
El valor después de 5 operaciones para eliminar los 5 caracteres de String aabbc es 5.
Enfoque ingenuo: la idea es verificar si la string está vacía o no . Si no está vacío, los siguientes son los pasos para resolver el problema:
- Encuentre la primera aparición de los alfabetos más pequeños en la string actual, digamos ind y elimínelos de la string.
- Aumente el conteo por ind + 1.
- Repita el paso anterior hasta que la string quede vacía.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <string>
using namespace std;
// Function to find the value after
// N operations to remove all the N
// characters of string S
void charactersCount(string str, int n)
{
int count = 0;
// Iterate till N
while (n > 0) {
char cur = str[0];
int ind = 0;
for (int j = 1; j < n; j++) {
if (str[j] < cur) {
cur = str[j];
ind = j;
}
}
// Remove character at ind and
// decrease n(size of string)
str.erase(str.begin() + ind);
n--;
// Increase count by ind+1
count += ind + 1;
}
cout << count << endl;
}
// Driver Code
int main()
{
// Given string str
string str = "aabbc";
int n = 5;
// Function call
charactersCount(str, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the value after
// N operations to remove all the N
// characters of String S
static void charactersCount(String str, int n)
{
int count = 0;
// Iterate till N
while (n > 0)
{
char cur = str.charAt(0);
int ind = 0;
for(int j = 1; j < n; j++)
{
if (str.charAt(j) < cur)
{
cur = str.charAt(j);
ind = j;
}
}
// Remove character at ind and
// decrease n(size of String)
str = str.substring(0, ind) +
str.substring(ind + 1);
n--;
// Increase count by ind+1
count += ind + 1;
}
System.out.print(count + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given String str
String str = "aabbc";
int n = 5;
// Function call
charactersCount(str, n);
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program for the above approach # Function to find the value after # N operations to remove all the N # characters of String S def charactersCount(str, n): count = 0; # Iterate till N while (n > 0): cur = str[0]; ind = 0; for j in range(1, n): if (str[j] < cur): cur = str[j]; ind = j; # Remove character at ind and # decrease n(size of String) str = str[0 : ind] + str[ind + 1:]; n -= 1; # Increase count by ind+1 count += ind + 1; print(count); # Driver Code if __name__ == '__main__': # Given String str str = "aabbc"; n = 5; # Function call charactersCount(str, n); # This code is contributed by Amit Katiyar
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the value after
// N operations to remove all the N
// characters of String S
static void charactersCount(String str, int n)
{
int count = 0;
// Iterate till N
while (n > 0)
{
char cur = str[0];
int ind = 0;
for(int j = 1; j < n; j++)
{
if (str[j] < cur)
{
cur = str[j];
ind = j;
}
}
// Remove character at ind and
// decrease n(size of String)
str = str.Substring(0, ind) +
str.Substring(ind + 1);
n--;
// Increase count by ind+1
count += ind + 1;
}
Console.Write(count + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given String str
String str = "aabbc";
int n = 5;
// Function call
charactersCount(str, n);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to find the value after
// N operations to remove all the N
// characters of String S
function charactersCount(str, n)
{
let count = 0;
// Iterate till N
while (n > 0)
{
let cur = str[0].charCodeAt();
let ind = 0;
for(let j = 1; j < n; j++)
{
if (str[j].charCodeAt() < cur)
{
cur = str[j].charCodeAt();
ind = j;
}
}
// Remove character at ind and
// decrease n(size of String)
str = str.substring(0, ind) +
str.substring(ind + 1);
n--;
// Increase count by ind+1
count += ind + 1;
}
document.write(count + "</br>");
}
// Given String str
let str = "aabbc";
let n = 5;
// Function call
charactersCount(str, n);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
5
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver utilizando el concepto de árbol de índice binario o árbol de Fenwick . A continuación se muestran los pasos:
- Inicialmente, almacene los valores de los índices de todos los caracteres/alfabeto en orden creciente.
- Comience con el alfabeto ‘a’ más pequeño y elimine todas las ‘a’ en el orden en que aparecen. Después de eliminar, seleccione el siguiente alfabeto ‘b’ y repita este paso hasta que se eliminen todos los alfabetos.
- Eliminar el carácter significa que su valor correspondiente en la array se cambia a 0 , lo que indica que se eliminó.
- Antes de eliminar, encuentre la posición del carácter en la string usando el método sum() en Fenwick Tree y agregue el valor de posición al conteo.
- Después de eliminar todos los caracteres de la string, se obtiene el valor de cuenta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of Fenwick tree
struct FenwickTree {
// Binary indexed tree
vector<int> bit;
// bit[0] is not involved
int n;
// Constructor
FenwickTree(int n)
{
this->n = n + 1;
bit = vector<int>(n, 0);
}
// Constructor
FenwickTree(vector<int> a)
: FenwickTree(a.size())
{
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
// Sum of arr[0] + arr[1] + ...
// + arr[idx] where arr is array
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;
}
// Function for adding arr[idx]
// is equals to arr[idx] + val
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);
}
}
// Update the index
void update(int idx, int val)
{
add(idx, val - valat(idx));
}
// Perform the sum arr[l] + arr[l+1]
// + ... + arr[r]
int sum(int l, int r)
{
return sum(r) - sum(l - 1);
}
int valat(int i)
{
return sum(i, i);
}
void clr(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 count the characters
void charactersCount(string str, int n)
{
int i, count = 0;
// Store the values of indexes
// for each alphabet
vector<vector<int> > mp
= vector<vector<int> >(26,
vector<int>());
// Create FenwickTree of size n
FenwickTree ft = FenwickTree(n);
ft.clr(n);
// Initially no indexes are
// stored for each character
for (i = 0; i < 26; i++)
mp[i].clear();
i = 0;
for (char ch : str) {
// Push 'i' to mp[ch]
mp[ch - 'a'].push_back(i);
i++;
}
// Start with smallest character
// and move towards larger character
// i.e., from 'a' to 'z' (0 to 25)
for (i = 0; i < 26; i++) {
// index(ind) of current character
// corres to i are obtained
// in increasing order
for (int ind : mp[i]) {
// Find the number of characters
// currently present before
// ind using ft.sum(ind)
count += ft.sum(ind);
// Mark the corresponding
// ind as removed and
// make value at ind as 0
ft.update(ind, 0);
}
}
// Print the value of count
cout << count << endl;
}
// Driver Code
int main()
{
// Given string str
string str = "aabbc";
int n = 5;
// Function call
charactersCount(str, n);
return 0;
}
Java
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of Fenwick tree
struct FenwickTree {
// Binary indexed tree
vector<int> bit;
// bit[0] is not involved
int n;
// Constructor
FenwickTree(int n)
{
this->n = n + 1;
bit = vector<int>(n, 0);
}
// Constructor
FenwickTree(vector<int> a)
: FenwickTree(a.size())
{
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
// Sum of arr[0] + arr[1] + ...
// + arr[idx] where arr is array
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;
}
// Function for adding arr[idx]
// is equals to arr[idx] + val
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);
}
}
// Update the index
void update(int idx, int val)
{
add(idx, val - valat(idx));
}
// Perform the sum arr[l] + arr[l+1]
// + ... + arr[r]
int sum(int l, int r)
{
return sum(r) - sum(l - 1);
}
int valat(int i)
{
return sum(i, i);
}
void clr(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 count the characters
void charactersCount(string str, int n)
{
int i, count = 0;
// Store the values of indexes
// for each alphabet
vector<vector<int> > mp
= vector<vector<int> >(26,
vector<int>());
// Create FenwickTree of size n
FenwickTree ft = FenwickTree(n);
ft.clr(n);
// Initially no indexes are
// stored for each character
for (i = 0; i < 26; i++)
mp[i].clear();
i = 0;
for (char ch : str) {
// Push 'i' to mp[ch]
mp[ch - 'a'].push_back(i);
i++;
}
// Start with smallest character
// and move towards larger character
// i.e., from 'a' to 'z' (0 to 25)
for (i = 0; i < 26; i++) {
// index(ind) of current character
// corres to i are obtained
// in increasing order
for (int ind : mp[i]) {
// Find the number of character
// currently present before
// ind using ft.sum(ind)
count += ft.sum(ind);
// Mark the corresponding
// ind as removed and
// make value at ind as 0
ft.update(ind, 0);
}
}
// Print the value of count
cout << count << endl;
}
// Driver Code
int main()
{
// Given string str
string str = "aabbc";
int n = 5;
// Function call
charactersCount(str, n);
return 0;
}
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Structure of Fenwick tree
public class FenwickTree
{
// Binary indexed tree
public int []bit;
// bit[0] is not involved
int n;
// Constructor
public FenwickTree(int n)
{
this.n = n + 1;
bit = new int[n];
}
// Constructor
public FenwickTree(List<int> a)
{
for(int i = 0; i < a.Count; i++)
add(i, a[i]);
}
// Sum of arr[0] + arr[1] + ...
// + arr[idx] where arr is array
public 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;
}
// Function for adding arr[idx]
// is equals to arr[idx] + val
public 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);
}
}
// Update the index
public void update(int idx, int val)
{
add(idx, val - valat(idx));
}
// Perform the sum arr[l] + arr[l+1]
// + ... + arr[r]
public int sum(int l, int r)
{
return sum(r) - sum(l - 1);
}
public int valat(int i)
{
return sum(i, i);
}
public void clr(int sz)
{
n = sz + 1;
bit = new int[n + 1];
// Initially mark all
// are present (i.e. 1)
for(int i = 0; i < n; i++)
add(i, 1);
}
};
// Function to count the characters
static void charactersCount(String str, int n)
{
int i, count = 0;
// Store the values of indexes
// for each alphabet
List<int> []mp = new List<int>[26];
for(i = 0; i < mp.Length; i++)
mp[i] = new List<int>();
// Create FenwickTree of size n
FenwickTree ft = new FenwickTree(n);
ft.clr(n);
// Initially no indexes are
// stored for each character
for(i = 0; i < 26; i++)
mp[i].Clear();
i = 0;
foreach(char ch in str.ToCharArray())
{
// Push 'i' to mp[ch]
mp[ch - 'a'].Add(i);
i++;
}
// Start with smallest character
// and move towards larger character
// i.e., from 'a' to 'z' (0 to 25)
for(i = 0; i < 26; i++)
{
// index(ind) of current character
// corres to i are obtained
// in increasing order
foreach(int ind in mp[i])
{
// Find the number of characters
// currently present before
// ind using ft.sum(ind)
count += ft.sum(ind);
// Mark the corresponding
// ind as removed and
// make value at ind as 0
ft.update(ind, 0);
}
}
// Print the value of count
Console.Write(count + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given String str
String str = "aabbc";
int n = 5;
// Function call
charactersCount(str, n);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript program for the above approach
// Structure of Fenwick tree
class FenwickTree
{
constructor(n)
{
this.n = n + 1;
this.bit = new Array(n);
}
_FenwickTree(a)
{
for(let i = 0; i < a.length; i++)
this.add(i, a.get(i));
}
// Sum of arr[0] + arr[1] + ...
// + arr[idx] where arr is array
sum(idx)
{
let 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 += this.bit[idx];
// Move index to parent
// node in getSum View
idx -= idx & (-idx);
}
// Return the result
return ret;
}
// Function for adding arr[idx]
// is equals to arr[idx] + val
add(idx,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 <= this.n)
{
// Add 'val' to current
// node of BI Tree
this.bit[idx] += val;
// Update index to that
// of parent in update View
idx += idx & (-idx);
}
}
// Update the index
update(idx,val)
{
this.add(idx, val - this.valat(idx));
}
// Perform the sum arr[l] + arr[l+1]
// + ... + arr[r]
_sum(l,r)
{
return this.sum(r) - this._sum(l - 1);
}
valat(i)
{
return this.sum(i, i);
}
clr(sz)
{
this.n = sz + 1;
this.bit = new Array(this.n + 1);
for(let i=0;i<this.n+1;i++)
this.bit[i]=0;
// Initially mark all
// are present (i.e. 1)
for(let i = 0; i < n; i++)
this.add(i, 1);
}
}
// Function to count the characters
function charactersCount(str,n)
{
let i, count = 0;
// Store the values of indexes
// for each alphabet
let mp = new Array(26);
for(i = 0; i < mp.length; i++)
mp[i] = [];
// Create FenwickTree of size n
let ft = new FenwickTree(n);
ft.clr(n);
// Initially no indexes are
// stored for each character
for(i = 0; i < 26; i++)
mp[i]=[];
i = 0;
for(let ch of str.split("").values())
{
// Push 'i' to mp[ch]
mp[ch.charCodeAt(0) - 'a'.charCodeAt(0)].push(i);
i++;
}
// Start with smallest character
// and move towards larger character
// i.e., from 'a' to 'z' (0 to 25)
for(i = 0; i < 26; i++)
{
// index(ind) of current character
// corres to i are obtained
// in increasing order
for(let ind of mp[i].values())
{
// Find the number of characters
// currently present before
// ind using ft.sum(ind)
count += ft.sum(ind);
// Mark the corresponding
// ind as removed and
// make value at ind as 0
ft.update(ind, 0);
}
}
// Print the value of count
document.write(count + "<br>");
}
// Driver Code
// Given String str
let str = "aabbc";
let n = 5;
// Function call
charactersCount(str, n);
// This code is contributed by unknown2108
</script>
Producción:
5
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saideepgummadavelly y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA