Min String : Multi DP

#1

Unable to apprach the question. Please help

#2

Hi @aman2382000

this q can be approached using 3-d dp on the number of characters present in the string namely a,b,c.
Divide the approach into 3 parts, 1) when only single type of letter is present ; 2) when only 2 types of letters are present ; 3) all 3 types of letters are present. try top down approach now .

Hope it helps.

#3

Can you please provide the implementation part for this.

#4

These are the functions, now try to solve yourself.
Link : https://ide.codingblocks.com/s/206033

Hope it Helps.

#5

Thank you. But if we have a string bbca, then why are we calling dum(a-1,b-1,c+1) because b and a cannot be combined. So why are we looking only at the number of characters and not the their pos ?

#6

It won’t matter as we are already taking minimum of all three types of operations and also it can be possible at a later stage -> bbca -> baa -> ca -> b. You will get correct answer then also.

Hope it helps.

#7

@aman2382000
Please mark your doubt as resolved.