Минимальный символ, который необходимо удалить

Оригинальная проблема:

Слово было K-хорошим, если для каждые две буквы в слове, если первый появляется x раз, а второй появляется y раз, тогда |x - y| ≤ K.

Учитывая некоторое слово w, сколько букв он должен удалить, чтобы сделать его K-хорошим?
Ссылка на проблему.

Я решил эту проблему и не просил решения для вышеперечисленного Проблема

Я просто неправильно прочитал выражение в первый раз и просто подумал, как мы можем решить эту проблему в линейном времени линии, что только порождает новую проблему



Проблема модификации

Слово было K-хорошим, если для каждого двух последовательных букв в слове, если первый появляется x раз, а второй появляется y раз, тогда |x - y| ≤ K.

Учитывая некоторое слово w, сколько букв ему нужно удалить, чтобы сделать его K-хорошим?

Является ли эта проблема разрешимой в линейном времени, я подумал об этом, но не нашел подходящего решения.

Решение

Мой подход: я не мог подойти к моей давке, но она - мой подход к этой проблеме, попробуйте все (из фильма Zooptopia)

то есть. 

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

Для N в диапазоне 10^5. Сложность времени: времени в этом измерении не существует.

Есть ли линейное решение этой проблемы, простое и приятное, как люди 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

Я думаю, что это простой пример, я могу более сложный пример как удаление I-элемента makens (I-1) и (I + 1) в качестве последовательного

Ответы

Ответ 1

Существует ли линейное решение этой проблемы?

Рассмотрим слово DDDAAABBDC. Это слово является 3-хорошим, потому что D и C являются последовательными и card(D)-card(C)=3, а удаление последнего D делает его 1-хорошим, делая D и C не последовательными.

И наоборот, если я считаю DABABABBDC, который является 2-хорошим, удаление последнего D делает C и B последовательным и увеличивает значение K слова до 3.

Это означает, что в модифицированной задаче значение K слова определяется как кардиналами каждой буквы, так и кардиналами каждой пары последовательных букв.

Удалив букву, я уменьшаю ее кардинал буквы, а также кардиналы пар, к которым она принадлежит, но я также увеличиваю кардинал другой пары (потенциально создавая новые).

Также важно заметить, что если в исходной задаче все буквы эквивалентны (я могу удалить их безразлично), а в измененной задаче это уже не так.

В качестве вывода я считаю, что мы можем смело предположить, что ограничение "последовательных букв" делает проблему не разрешимой в линейном времени для любого алфавита/слова.

Ответ 2

Вместо поиска линейного решения времени, которое, как я думаю, не существует (в том числе потому, что, как представляется, существует множество альтернативных решений для каждого запроса K), я бы хотел установить решение полностью geeky.

А именно, возьмите язык обработки параллельного массива Dyalog APL и создайте эти две крошечные динамические функции:

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)/¨⊂⍵}

good сообщает нам K-доброту строки. Несколько примеров ниже:

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

make принимает в качестве аргументов

[desired K] make [any string]

и возвращает  - оригинальная строка
 - K для оригинальной строки
 - уменьшенная строка для желаемого K
 - сколько персонажей было удалено для достижения  - сколько возможных решений для достижения желаемого K

Например:

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

Немного длиннее строка:

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

Можно увеличивать и уменьшать K-доброту.

К сожалению, это грубая сила. Мы генерируем 2-базу всех целых чисел между 2 ^ [длина строки] и 1, например:

0 1 0 1 1

Затем мы проверяем доброту подстроки, например:

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

Мы выбираем только те результаты (подстроки), которые соответствуют желаемому K-хорошему. Наконец, из множества возможных результатов мы выбираем первый, который остается с большинством оставшихся символов.

По крайней мере, это было забавно для кода: -).