Wednesday 5 August 2015

Remove couples from a string

Given a string of some symbols, write a program to transform a string by repeatedly eliminating two same symbols occurring together.

For example

1. “ABCCAB” is transformed to “ABAB”
2. “ABCCBD” is transformed to “AD”
         “ABCCBD” -> “ABBD” -> “AD”

We can solve this problem using stack data structure.
1.   Read String character by character.
If top element of stack is equal to this character, then pop it, else push this character.

         Repeat above procedure until end of the string, finally stack contains our output.
import java.util.LinkedList;
import java.util.Objects;

public class StringCouple {

 public static String decoupleString(String str) {
  Objects.nonNull(str);
  if (str.length() < 2)
   return str;

  LinkedList<Character> list = new LinkedList<>();

  list.push(str.charAt(0));

  for (int i = 1; i < str.length(); i++) {
   if (list.size() > 0 && list.peek() == str.charAt(i)) {
    list.pop();
   } else {
    list.push(str.charAt(i));
   }
  }

  StringBuilder sb = new StringBuilder(list.size());
  for (Character c : list)
   sb.append(c);
  return sb.reverse().toString();
 }
}


Following is the junit test case for above program.
import static org.junit.Assert.*;

import org.junit.*;

public class StringCoupleTest {

 @Test
 public void test1(){
  assertEquals(StringCouple.decoupleString("ABCCAB"), "ABAB");
  assertEquals(StringCouple.decoupleString("ABCCBD"), "AD");
  assertEquals(StringCouple.decoupleString("GBRRBR"), "GR");
  assertEquals(StringCouple.decoupleString("BGRGRR"), "BGRG");
  assertEquals(StringCouple.decoupleString("GGBB"), "");
  assertEquals(StringCouple.decoupleString("RGBGBR"), "RGBGBR");
 }
}


No comments:

Post a Comment