### Just_LOL's blog

By Just_LOL, history, 6 weeks ago,

You are given an string s of length n. And there is a eraser and it deletes neighboring characters of a particular letter when it place on a specific position. For an example 'aaaaba' when we place eraser on 1st 'a'(index 0), string becomes 'ba' (since we deleted all the letters of the neighboring 'a's). Task is to delete the entire string in minimum operations.

Test 1
Input -> 6 aabcbb
Output -> 3

Constraints
1<=n<=1000

• 0

 » 6 weeks ago, # | ← Rev. 7 →   +3 cout << (n+2)/3 << endl; Assuming it can erase both neighbours at same time. So elimininate 3 in one go.Edit: This is wrong. By neighbours, it means all consecutive neighbours that are same, not just adjacent.
•  » » 6 weeks ago, # ^ |   0 but it didn't work
•  » » » 6 weeks ago, # ^ |   0 Can you share the problem link?
•  » » » » 6 weeks ago, # ^ |   0 I sent the link as a message
•  » » » » » 6 weeks ago, # ^ |   0 Problem LinkLanguage of submission is ADA, no other language, I can't code it there.I think problem is not so easy as it seems. My approach would be to use 2d DP. dp[i][j] represents minimum operation to erase string from i to j. Then for example in string "bbbabaabaa" I would try to erase all subtrings between consecutive 'b' recursively using minimum operations, and then at last delete all 'b' in one go. I would do this for all characters from 'a' to 'z'. Complexity would be O(26*N*N). Problem doesn't allow C++, or I would've tested it.
•  » » » » » » 6 weeks ago, # ^ |   0 But I coded in C++. I think u didn't choose the correct language
 » 6 weeks ago, # |   0 just do exactly what eraser do: int i=0,ans=0; while(i
•  » » 6 weeks ago, # ^ |   0 This works well. But it will not give the optimal answer. Need to do with minimum operations
•  » » » 6 weeks ago, # ^ |   0 please provide a counter test for this case
•  » » » » 6 weeks ago, # ^ |   +3 bbbabaabaaOptimal answer is 4, but your answer is 6
•  » » » » 6 weeks ago, # ^ |   0 Let's consider string abaca.The correct answer is 3 but your algo gives 5.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Ahh , I understood the problem in wrong way
 » 6 weeks ago, # | ← Rev. 3 →   0 We may remove instantly all successive duplicates of elements, e. i., aaaaba => aba, as 1 eraser removes all equal elements. We can think of such dp: for i = n..1 for j = i..n if i == j dp[i][j] = 1 // we need exactly 1 eraser for 1 element else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + s[i] != s[j] ? 1 : 0 What are we doing here is we calculate the optimal answer for the ranges (i + 1, j) and (i, j - 1) and then combine them adding 1 eraser if edge elements are different.This should work, I hope it helps.
•  » » 6 weeks ago, # ^ |   0 Thanks a lot. I'll try and let u know.
 » 6 weeks ago, # | ← Rev. 3 →   0 This problem can be solved using range DP. $\text{ }\\ dp[i][i] = 1 \\dp[i][j] = \min \begin{cases}dp[i+1][j] + 1, \\ dp[i][j-1] + 1, \\ dp[i+1][j], & \text{if } a[i] = a[i+1]\\ dp[i][j-1], & \text{if } a[j] = a[j-1]\\ \min(dp[i+1][j], dp[i][j-1]), & \text{if } a[i] = a[j] \end{cases}$The solution comes from the fact that you do not need to perform extra operations on characters that are same to the next one.
•  » » 6 weeks ago, # ^ |   0 Thanks a lot. I'll try and let u know.