using System;

namespace Sandbox
{
	internal class Program
	{
		private static void Main(string[] args)
		{
			Program p = new Program();
			Console.WriteLine(p.Start(args));

			Console.WriteLine("\nPress <enter> to continue...");
			Console.ReadLine();
		}

		public bool Start(string[] args)
		{
			/*
				How would you solve this problem optimizely?
				Rearrange characters in a string so that no character repeats twice.
				Input: aaabc
				Output: abaca
				Input: aa
				Output: No valid output
				Input: aaaabc
				Output: No valid output
			*/

			char[] input = "aaabc".ToCharArray();
			char temp;
			bool swapfound = false;

			Console.WriteLine(input);
			for (int i = 0; i <= input.Length - 2; i++)
			{
				if (input[i] == input[i + 1]) // we have an adjacent match
				{
					swapfound = false;

					for (int d = i + 2; d <= input.Length - 1; d++)
					{
						if (input[d] != input[i + 1]) // search for swappable character
						{
							// swap adjacent match with found swappable character
							temp = input[d];
							input[d] = input[i + 1];
							input[i + 1] = temp;

							swapfound = true;
						}
					}

					if (!swapfound)
					{
						Console.WriteLine(input);
						return false;
					}
				}
			}

			Console.WriteLine(input);
			return true;
		}
	}
}