jd_sal's blog

Minimum string coefficient — Hackerrank
By jd_sal, history, 5 years ago, In English

I am not able to understand the solution of the last problem from Hack the interview II -Global, a contest on Hackerrank which finished few days ago.It's labelled 'HARD'.

Problem Link : (https://www.hackerrank.com/contests/hack-the-interview-ii-global/challenges/flipped-beauty/problem)

Solution Link : (https://www.hackerrank.com/rest/contests/hack-the-interview-ii-global/challenges/flipped-beauty/hackers/izban/download_solution)

Solution by Errichto : (https://www.hackerrank.com/rest/contests/hack-the-interview-ii-global/challenges/flipped-beauty/hackers/Errichto/download_solution)

I don't get what is len = m-2-2*p in the first solution ? Although both the solutions are same.

It will be really helpful if someone explains me the solution. Thanks!

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

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Suppose the string is "000100010011000". Intervals will be: {3,1,3,1,2,2,3}. So if I want my answer to be zero, the string will look like this 0000111111 or 11110000 (continuous 1's with continuous 0's or vice versa). so it can only be possible k<=(interval.size()-2)/2. (because we can skip the first 2 Interval element)

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

The final answer will be the length of a substring of the original string.

First, we will make an array which will contain values of continuous segments. For example s="00011001" then the array is {3,2,2,1}.

Now, we can see that the first and last values of this array won't contribute to our answer so it can be removed. Now, if you see the flip operation it is like removing 2 values from our array in the following 3 ways:

1- remove 2 values from the start

2- remove 2 values form the end

3- remove 1 from start and 1 from the end (can be done by flipping from start to end of the remaining string)

After observing above you can see that question has converted to find minimum subarray of size (n-2*p) where n is the size of the array.

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

    Thank you for your reply bro.Let's take s="1011010" and p=1.Then array of lengths of continuous segments will be [1,1,2,1,1,1].Let's take 1-based indexing. If we flip [3,4], then new array will be [1,4,1,1], then in this case how are we removing 2 values in the 3 ways you mentioned? Could you please do a little simulation of your idea because it's unclear to me.

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

      Our array is [1,1,2,1,1,1]. We know that the first and last values will not contribute to our answer. So we will remove that so new array will be [1,2,1,1]. In the optimal solution, you will only do those operations which can remove values from start and end part of the array because if we do the operation in the middle of the string it won't change our answer.

      Now, consider the string s="1011010" and p=1 .In the optimal solution, you won't flip [3,4]. Either you will flip [2,2] or [6,6] or [2,6] so that you can remove elements from the start and end of the array.

      → Reply