Code Forces Education Round 96 String Deletion help

help
1

can anyone explain me the code of STRING DELETION from this official tutorial .The approach is clear to me but i got TLE on TC 4. Thanks in advance :slight_smile:

2

you didn’t share your submission id and expecting for help. cool!!

1 Like
3

Yeah sure, you are getting a TLE as you used a map in line number 179 of your code, just reviewed your code in my dream :slightly_smiling_face:

1 Like
4

Thanks @cubefreak777 :slight_smile: I came in your dreams to check my code. Now i have removed that map and finally code is working and i got AC. This is my submission_id 95462414 and link but if you have any different approach plz explain! Thank you :slight_smile:

5

Submission #95462414 - Codeforces my submission link and now i got AC but if you have any better approach plz suggest Thank you!

6

I don’t know whether you did same as me but here’s my approach.
We’ve to two steps in one operation,

  1. Remove any character from string
  2. Remove prefix of same characters.

First convert the string into frequency array. i.e if we have 10001110100 then the frequency array will be [1,3,3,1,1,2]

now we’ve to maximize the number of moves, now if we have prefix of length > 1 then we can remove one character from that prefix and after that remove that prefix, by doing this we are not removing any extra character and it’ll maximize number of moves.

now if prefix of same characters has length = 1 then we’ll find next prefix with length > 1
remove one character from that (first step) and remove current prefix with length = 1 hence total number of characters removed = 2(in this case). we are doing this because if we’ll remove prefix of length = 1 (i.e one character) as our first step then there can be prefix of some larger length after current prefix, so we’ll have to remove whole prefix of that larger length
then the total number of character removed will be = 1 + prefix of length > 1.

Ex -
10001110100
[1,3,3,1,1,2]
prefix has length = 1, find prefix with length > 1 which is 3 at index 1 remove one character from that + prefix of length 1 hence array will become [0,2,3,1,12] continue for next index.

Now try to figure out what if all frequency are 1, i.e string is 10101010101. Find solution with this edge case.

Here’s my submission if it could help.