Minimum Character that needed to be deleted

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

2 Answers

Answers 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.

Answers 2

Let's say string length is N and we wanted to have a solution for N = 10^5.

One approach is to make a interval of allowed frequency of character. O(26N) or O(N) i.e. Linear with respect to string length.

1. You can make an array counting the frequency of different character.
2. Generate intervals lower_bound to upper_bound, such that upper_bound = lower_bound + K. Simply by iterating lower_bound from 1 to MAX_FREQUENCY and making upper_bound=lower_bound + K
   • For every character(a-z), calculate how many character to remove to make frequency comes within (lower_bound,upper_bound) or become equal to 0.
   • Sum up, required number of removal for this interval, let's say S.
3. Find the minimum of S.

If You Enjoyed This, Take 5 Seconds To Share It

• Facebook
• Twitter
• Google+
• StumbleUpon
• Digg
• Delicious
• LinkedIn
• Reddit
• Technorati