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