Minimum Character that needed to be deleted

Question

Original Problem:

A word was K-good if for every two letters in the word, if the first appears x times and the second appears y times, then |x - y| ≤ K.

Given some word w, how many letters does he have to remove to make it K-good?
Problem Link.

I have solved the above problem and i not asking solution for the above problem

I just misread the statement for first time and just thought how can we solve this problem in linear line time , which just give rise to a new problem

Modification Problem

A word was K-good if for every two consecutive letters in the word, if the first appears x times and the second appears y times, then |x - y| ≤ K.

Given some word w, how many letters does he have to remove to make it K-good?

Is this problem is solvable in linear time , i thought about it but could not find any valid solution.

Solution

My Approach: I could not approach my crush but her is my approach to this problem , try everything( from movie Zooptopia)

i.e.

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 

For N in Range 10^5. Time Complexity: Time does not exist in that dimension.

Is there any linear solution to this problem , simple and sweet like people of 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 guess this is a simple example there can me more complex example as deleting an I element makens (I-1) and (I+1) as consecutive

Answer 1

Is there any linear solution to this problem?

Consider the word DDDAAABBDC. This word is 3-good, becauseDandCare consecutive and card(D)-card(C)=3, and removing the lastDmakes it 1-good by makingDandCnon-consecutive.

Inversely if I consider DABABABBDC which is 2-good, removing the lastDmakes CandBconsecutive and increases the K-value of the word to 3.

This means that in the modified problem, the K-value of a word is determined by both the cardinals of each letter and the cardinals of each couple of consecutive letters.

By removing a letter, I reduce its cardinal of the letter as well as the cardinals of the pairs to which it belongs, but I also increase the cardinal of other pair (potentially creating new ones).

It is also important to notice that if in the original problem, all letters are equivalent (I can remove any indifferently), while it is no longer the case in the modified problem.

As a conclusion, I think we can safely assume that the "consecutive letters" constrain makes the problem not solvable in linear time for any alphabet/word.

Answer 2

Instead of finding the linear time solution, which i think doesn't exist (among others because there seem to be a multitude of alternative solutions to each K request), i'd like to preset the totally geeky solution.

Namely, take the parallel array processing language Dyalog APL and create these two tiny dynamic functions:

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 tells us the K-goodness of a string. A few examples below:

// 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 takes as arguments

[desired K] make [any string]

and returns
- original string
- K for original string
- reduced string for desired K
- how many characters were removed to achieve deired K
- how many possible solutions there are to achieve desired K

For example:

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

A little longer string:

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

It is possible to both increase and decrease the K-goodness.

Unfortunately, this is brute force. We generate the 2-base of all integers between 2^[lenght of string] and 1, for example:

0 1 0 1 1

Then we test the goodness of the substring, for example of:

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

We pick only those results (substrings) that match the desired K-good. Finally, out of the multitude of possible results, we pick the first one, which is the one with most characters left.

At least this was fun to code :-).