nisanduuu's blog

Please help me to solve this problem
By nisanduuu, history, 12 months ago, In English

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
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
12 months ago, # |
← Rev. 7   Vote: I like it +3 Vote: I do not like it 
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.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

just do exactly what eraser do:

int i=0,ans=0;
while(i<n){
   int j=i+1;
   while(j<n&&s[j]==s[i])j++;
   ans++;
   i=j;
}
cout<<ans<<endl;

I think this will work

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This works well. But it will not give the optimal answer. Need to do with minimum operations

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      please provide a counter test for this case

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        bbbabaabaa

        Optimal answer is 4, but your answer is 6

        → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Let's consider string abaca.

        The correct answer is 3 but your algo gives 5.

        → Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
  1. We may remove instantly all successive duplicates of elements, e. i., aaaaba => aba, as 1 eraser removes all equal elements.
  2. 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.

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply