Encuentre valor después de N operaciones para eliminar N caracteres de la string S con restricciones dadas

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *