minima carattere che doveva essere eliminato

Question

problema originale:

Una parola era K-buono se per ogni due lettere della parola, se il primo appare x volte e la seconda appare y volte, poi |x - y| ≤ K.

Data una parola w, quante lettere deve rimuovere per renderlo K-buono?
Problem Link.

ho risolto il problema di cui sopra e non mi chiede soluzione per quanto sopra problema

Ho appena letto male la dichiarazione per la prima volta e solo pensato come possiamo risolvere questo problema nel tempo la linea lineare, che ha appena dare origine ad un nuovo problema

Modifica problema

una parola era K-buono se per ogni due lettere consecutive nella parola, se il primo appare x volte e la seconda appare y volte, poi |x - y| ≤ K.

Data una parola w, quante lettere ha lui di rimuovere per renderlo K -bene?

Questo problema è risolvibile in tempo lineare, ci ho pensato ma non ho trovato nessuna soluzione valida.

Soluzione

mio approccio: non ho potuto avvicino al mio cotta, ma il suo è il mio approccio a questo problema, provare tutto (dal film Zooptopia)

cioè

for i range(0,1<<n): // n length of string 
    for j in range(0,n): 
      if(i&(1<<j) is not zero): delete the character 
    Now check if String is K good 

Per N nel range 10^5. Complessità del tempo: il tempo non esiste in quella dimensione.

Esiste una soluzione lineare a questo problema, semplice e dolce come le persone dello stackoverflow.

For Ex: 
String S = AABCBBCB and K=1 


    If we delete 'B' at index 5 so String S = AABCBCB which is good string 
    F[A]-F[A]=0 
    F[B]-F[A]=1 
    F[C]-F[B]=1 
    and so on 

Credo che questo è un semplice esempio lì mi esempio più complesso, come l'eliminazione di un io elemento makens (I-1) e (I + 1) come consecutiva

Answer 1

può C'è qualche soluzione lineare a questo problema?

Prendere in considerazione la parola DDDAAABBDC. Questa parola è 3-buona, perché D e C sono consecutive e card(D)-card(C)=3 e la rimozione dell'ultimo D lo rende 1-buono rendendo D e C non consecutivi.

Inversamente se ritengo DABABABBDC che è 2-buono, rimozione dell'ultimo D rende C e B consecutiva e aumenta il valore K di parola a 3.

Ciò significa che nel problema modificata, il K Il valore di una parola è determinato sia dai cardinali di ciascuna lettera sia dai cardinali di ciascuna coppia di lettere consecutive.

Rimuovendo una lettera, riduco il suo cardinale della lettera così come i cardinali delle coppie a cui appartiene, ma aumento anche il cardinale di un'altra coppia (potenzialmente creandone di nuovi).

È anche importante notare che se nel problema originale tutte le lettere sono equivalenti (posso rimuovere qualsiasi indifferentemente), mentre non è più il caso nel problema modificato.

In conclusione, penso che possiamo tranquillamente supporre che il vincolo "lettere consecutive" renda il problema non risolvibile in tempo lineare per qualsiasi alfabeto/parola.

Answer 2

Invece di trovare la soluzione di tempo lineare, che credo non esiste (tra gli altri, perché ci sembrano essere un gran numero di soluzioni alternative a ogni richiesta K), mi piacerebbe preimpostare la totalmente geeky soluzione.

Vale a dire, prendere la lingua elaborazione di array paralleli Dyalog APL e creare queste due piccole funzioni dinamiche:

good←{1≥⍴⍵:¯1 ⋄ b←(⌈/a←(∪⍵)⍳⍵)⍴0 ⋄ b[a]+←1 ⋄ ⌈/|2-/b[a]} 

make←{⍵,(good ⍵),a,⍺,(l-⍴a←⊃b),⍴b←(⍺=good¨b/¨⊂⍵)⌿(b←↓⍉~(l⍴2)⊤0,⍳2⊥(l←⍴⍵)⍴1)/¨⊂⍵} 

buona ci dice il K-bontà di una stringa. Alcuni esempi qui sotto:

// fn" means the fn executes on each of the right args 
good" 'AABCBBCB' 'DDDAAABBDC' 'DDDAAABBC' 'DABABABBDC' 'DABABABBC' 'STACKOVERFLOW' 
2 3 1 2 3 1 

fanno prende come argomenti

[desired K] make [any string] 

e restituisce
- stringa originale
- K per stringa originale
- ridotto stringa per K desiderato
- quanti personaggi sono stati rimossi per ottenere Kired D
- quante possibilità Le soluzioni ci sono per raggiungere desiderata K

Ad esempio:

3 make 'DABABABBDC' 
┌──────────┬─┬─────────┬─┬─┬──┐ 
│DABABABBDC│2│DABABABBC│3│1│46│ 
└──────────┴─┴─────────┴─┴─┴──┘ 

Un po stringa superiore:

1 make 'ABCACDAAFABBC' 
┌─────────────┬─┬────────┬─┬─┬────┐ 
│ABCACDAAFABBC│4│ABCACDFB│1│5│3031│ 
└─────────────┴─┴────────┴─┴─┴────┘ 

È possibile sia aumentare e diminuire il K-bontà.

Sfortunatamente, questa è forza bruta.Generiamo il 2-base di tutti gli interi tra 2^[lunghezza della stringa] e 1, per esempio:

0 1 0 1 1 

Poi abbiamo testare la bontà della sottostringa, ad esempio di:

0 1 0 1 1/'STACK' // Substring is now 'TCK' 

Selezioniamo solo quei risultati (sottostringhe) che corrispondono al K-buono desiderato. Alla fine, fuori dalla moltitudine di possibili risultati, scegliamo il primo, che è quello con la maggior parte dei caratteri rimasti.

Almeno questo è stato divertente da codificare :-).