Migliorare l'algoritmo per la rimozione dell'elemento

Question

Problema

data una stringa s e m query. Per ogni query eliminare l'occorrenza K -th di un carattere x.

Ad esempio:

abcdbcaab 
5 
2 a 
1 c 
1 d 
3 b 
2 a 

Ans abbc 

Il mio approccio

Sto usando albero BIT per operazione di aggiornamento.

Codice:

for (int i = 0; i < ss.length(); i++) { 

    char cc = ss.charAt(i); 
    freq[cc-97] += 1; 
    if (max < freq[cc-97]) max = freq[cc-97]; 
    dp[cc-97][freq[cc-97]] = i;     // Counting the Frequency 
} 
BIT = new int[27][ss.length()+1]; 
int[] ans = new int[ss.length()]; 
int q = in.nextInt(); 
for (int i = 0; i < q; i++) { 
    int rmv = in.nextInt(); 
    char c = in.next().charAt(0); 

    int rr = rmv + value(rmv, BIT[c-97]);    // Calculating the original Index Value 
    ans[dp[c-97][rr]] = Integer.MAX_VALUE; 

    update(rmv, 1, BIT[c-97], max);   // Updating it 
} 
for (int i = 0; i < ss.length(); i++) { 
    if (ans[i] != Integer.MAX_VALUE) System.out.print(ss.charAt(i)); 
} 

complessità temporale è O(M log N) dove N è la lunghezza di corda ss.

Domanda

La mia soluzione mi dà Tempo Limite errore superato. Come posso migliorarlo?

public static void update(int i , int value , int[] arr , int xx){ 
    while(i <= xx){ 
     arr[i ]+= value; 
     i += (i&-i); 
    } 
} 

public static int value(int i , int[] arr){ 
    int ans = 0; 

    while(i > 0){ 
     ans += arr[i]; 
     i -= (i &- i); 
    } 
    return ans ; 
} 

Answer 1

Non ci sono operazioni chiave non mostrati, e le probabilità sono che uno di loro (molto probabilmente il metodo update) ha un costo diverso di quanto si pensi. Inoltre, la tua complessità dichiarata è sicuramente sbagliata perché ad un certo punto devi scansionare la stringa che è al minimo O(N).

Ma in ogni caso la strategia ovviamente giusta qui è quella di passare attraverso le query, separarle per carattere, e quindi passare attraverso le query in ordine inverso per capire le posizioni iniziali dei personaggi da sopprimere. Quindi esegui una volta la stringa, emettendo i caratteri solo quando si adatta. Questa soluzione, se implementata correttamente, dovrebbe essere possibile in O(N + M log(M)).

La sfida è come rappresentare le eliminazioni in modo efficiente. Sto pensando ad una sorta di albero di offset relativo in modo tale che se trovi che la prima cancellazione è stata 3 a, puoi inserirla in modo efficiente nell'albero e spostarla dopo ogni eliminazione successiva. Questo è dove sarà il bit log(M).