Rearrange characters in a string such that there is no consecutive occurrence of the same character

Rearrange characters in a string such that there is no consecutive occurrence of the same character.
Input: aaabc
Output: abaca

Input: aa
Output: No valid output

Input: aaaabc
Output: No valid output

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    class Program
    {
        static string str = "aabbbcccc";
        static int N = str.Length;
        static void Main(string[] args)
        {
            Console.WriteLine("Given string: " + str);

            //Initialize the board array to 0
            int[,] board = new int[N, N];
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    board[i, j] = 0;
                }
            }

            //Initialize the pointer array
            int[] pointer = new int[N];
            for (int i = 0; i < N; i++)
            {
                pointer[i] = -1;
            }

            //Implementation of Back Tracking Algorithm
            for (int j = 0; ;)
            {
                pointer[j]++;
                //Reset and move one column back 
                if (pointer[j] == N)
                {
                    board[pointer[j] - 1, j] = 0;
                    pointer[j] = -1;
                    j--;
                    if (j == -1)
                    {
                        Console.WriteLine("No valid rearrangement possible...");
                        break;
                    }
                }
                else
                {
                    board[pointer[j], j] = 1;
                    if (pointer[j] != 0)
                    {
                        board[pointer[j] - 1, j] = 0;
                    }
                    if (SolutionCheck(board))
                    {
                        j++;//move to next column
                        if (j == N)
                        {
                            break;
                        }
                    }
                }
            }
        }
        public static bool SolutionCheck(int[,] board)
        {
            //Row check
            string tempStr = "";
            for (int i = 0; i < N; i++)
            {
                int sum = 0;
                for (int j = 0; j < N; j++)
                {
                    sum = sum + board[i, j];
                    if(board[i, j] == 1)
                    {
                        tempStr = tempStr + str.Substring(j, 1);
                    }
                }
                if (sum > 1)
                {
                    return false;
                }
            }
            
            //Repetition Check
            if (tempStr.Length == str.Length)
            {
                for (int i = 0; i < tempStr.Length - 1; i++)
                {
                    if (tempStr.Substring(i, 1) == tempStr.Substring(i + 1, 1))
                    {
                        return false;
                    }
                }
                Console.WriteLine("Solution:");
                for (int i = 0; i < N; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        Console.Write(board[i, j] + " ");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine("Rearranged string: " + tempStr);
            }
            return true;
        }
    }
}

Output
=======
Given string: aabbbcccc
Solution:
1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1
Rearranged string: acabcbcbc
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s