Find Colored Couples

In an array of colors, we need to find out the no.of colored couples of the same color that are next to each other. If you find a colored couple, then you can remove that couple, and check whether any more couples can be formed by that or not.

Example

R G B B G R Y W Y

In the above, there are two B's next to each other. That is one couple, and we can remove that. After removing both the B's, the colors would be like

R G G R Y W Y

Now, there is another pair of G's in this. After removing that, the colors would be like below.

R R Y W Y

after removing R, it would be like below.

Y W Y.

At this time, there are no colored couples that are next to each other. In this case, there are three couples in the given array.


Answer:

Stack:

Stack is the simplest approach to solve this problem. If we can modify the input array, then we can use the input array itself as stack to solve this problem.

We take the first element, and push it to the stack.

If the stack contains any elements, then we take the top element and take the next element in the input array and compare the elements. If both are same, then we found one couple. We pop the element, and we move forward.

If the elements are not same, then we just push that element to the stack and proceed.

With this, by the time we reach the end, we would find the total no. of paired couples.


Doubly Linked List:

If the input elements is given in the form of Doubly Linked List, and if we can modify the input, then from that also, we can easily find the count.

We will have two pointers. Initially, first pointer would point to first element, and second pointer would point to second element. If both are different, then both pointers would move one step forward. If they are same, then the first pointer would move backward, and second pointer would move forward. We also would clear the two colors, and adjust the pointers in the doubly linked list. We repeat the loop.


Code for Stack:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
class color
{
 private:
 char *array;
 int length;

 public:

 void init(char *c) 
 {
  array = c;
  length = 0;
 };
 
 void push(char x)
 {
  array[length] = x;
  length++;
 };

 char pop() { return array[--length]; };

 char top() { return array[length-1]; };

 int exists() { return length; };
};

main(int argc, char **argv)
{
 char a[1000];
 int n, i, j, c=0;
 if(argc != 2) {
  printf("Usage: colorpairs colorstring\n");
  return -1;
 }
 strcpy(a, argv[1]);
 n = strlen(a);

 class color clr;
 clr.init(a);
 clr.push(a[0]);
 for(int k=1; k<n; k++) {
  if(clr.exists() && clr.top() == a[k]) {
   clr.pop();
   c++;
  } else {
   clr.push(a[k]);
  }
 }
 printf("Count: %d\n", c);
 return 0;
}

Code for Doubly Linked List:

findCount(Node *head)
{
 if(head == NULL || head->next == NULL)
  return 0;

 Node *first = head;
 Node *second = head->next;
 Node *free1, *free2;
 int count = 0;

 while(second != NULL) {
  if(first->value == second->value) {
   count++;
   free1 = first;
   free2 = second;

   if(second->next == NULL) 
    break;

   if(first->prev == NULL) {
    first = second->next;
    second = second->next->next;
   } else {
    first = first->prev;
    second = second->next;
   }

   first->next = second;
   second->prev = first;   

   free(free1);
   free(free2);
  } else {
   first = first->next;
   second = second->next;
  }
 }
 return count;
}