I_love_Saundarya's blog

How do I find the minimum number of operations?
By I_love_Saundarya, history, 6 years ago, In English

Problem-link : — https://www.hackerearth.com/practice/algorithms/dynamic-programming/2-dimensional/practice-problems/algorithm/shift-the-array-4074fac2/

You are given a string that contains lowercase English letters. In one step, you can choose a character and assign the next letter in the alphabet to it. (a-->b,b-->c,etc..and yea,z--->a). The number of indices where a[i]!=a[i+1] is given as f(string).

You are given a number 'k'.Now, your task is to determine the minimum number of steps required to perform on the string to obtain a string such that f(new-string)<=k.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

you can use dp(pos, current_letter, misses). current_letter forces than a[pos] = current_letter + 'a' (0 <= current_letter < 26)

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +8 Vote: I do not like it

(del)

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

(del)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is very similar to https://mirror.codeforces.com/contest/1108/problem/D .

→ Reply