Line Cut Algorithm Solution

Question

I am preparing for the interview that I have on Monday, and I decided to solve this problem: " String Reduction ". The problem is this:

For a string consisting of a, b, and c, we can perform the following operation: take any two adjacent separate characters and replace them with the third character. For example, if "a" and "c" are adjacent, they can be replaced with "b". What is the smallest line that can result by reapplying this operation?

For example, cab → cc or cab → bb, the result is a string of length 2. For this, one optimal solution is: bcab → aab → ac → b. No more operations can be applied, and the resulting line is 1. If the line is = UDPC, no operations can be performed, and so the answer is 5.

I saw a lot of questions and answers on stackoverflow, but I would like to test my own algorithm. Here is my pseudo-code algorithm. In my code

• S is my line for shorthand
• S [i] - character with index i
• P is the stack:

• redux is a function that reduces characters.

  function reduction(S[1..n]){ P = create_empty_stack(); for i = 1 to n do car = S[i]; while (notEmpty(P)) do head = peek(p); if( head == car) break; else { popped = pop(P); car = redux (car, popped); } done push(car) done return size(P)} 

In the worst case, my algorithms are O (n), because all operations on the glass P are on O (1). I tried this algorithm in the above examples, I get the expected answers. Let me execute my algorithm with this "abacbcaa" example:

 i = 1 : car = S[i] = a, P = {∅} P is empty, P = PU {car} -> P = {a} i = 2 : car = S[i] = b, P = {a} P is not empty : head = a head != car -> popped = Pop(P) = a car = reduction (car, popped) = reduction (a,b) = c P = {∅} push(car, P) -> P = {c} i = 3 : car = S[i] = a, P = {c} P is not empty : head = c head != car -> popped = Pop(P) = c car = reduction (car, popped) = reduction (a,c) = b P = {∅} push(car, P) -> P = {b} ... i = 5 : (interesting case) car = S[i] = c, P = {c} P is not empty : head = c head == car -> break push(car, P) -> P = {c, c} i = 6 : car = S[i] = b, P = {c, c} P is not empty : head = c head != car -> popped = Pop(P) = c car = reduction (car, popped) = reduction (b,c) = a P = {c} P is not empty : // (note in this case car = a) head = c head != car -> popped = Pop(P) = c car = reduction (car, popped) = reduction (a,c) = b P = {∅} push(car, P) -> P = {b} ... and it continues until n 

I run this algorithm with various examples like this, it works. I wrote Java code that checks this algorithm, when I submit my code to the system, I get the wrong answers. I posted java code on gisthub so you can see it.

Can someone tell me what is wrong with my algorithm.

Answer 1

I will try to explain what nhahtdh means. There are several reasons why your algorithm fails. But the most fundamental is that at each moment of time only the first character observed has a chance to get on the stack p . This should not be the case, since you can start the reduction mainly from any position.

Let me specify the string abcc . If a breakpoint at

 car = S[i]; 

The algorithm runs as:

 p = {∅}, s = _abcc //underscore is the position p = {a}, s = a_bcc p = {c}, s = ab_cc 

At this point you are stuck with a decrease in ccc

But there is another shortcut: abcc -> aac ->ab ->c

In addition, it is incorrect to return the stack size p . cc cannot be reduced, but the algorithm will return 1 . You should also count the number of passes.

Answer 2

you can also solve this issue using brute force ... and recursion

 for all n-1 pairs(2 char) replace it with 3rd char if possible and apply reduce on this new string of length n-1 for all n-2 pairs replace it with 3rd char and apply reduce on new string for all n-3 pairs....and so on 

A new line of length n-1 will have n-2 pairs, and similarly a new line of length n-2 will have n-3 pairs.

when using this approach, keep the minimum value

 if (new_min < min) min = new_min 

Implementation: http://justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html