paku
BAN USERhere is C# version of solution. i have used stack & hashset to build result . it will be defiantly less than O(2*N)
static void Main(string[] args)
{
do
{
Console.WriteLine("please enter string");
var str = Console.ReadLine();
var result = LexicoGraphical(str);
Console.WriteLine("LexicoGraphical order string is {0}\npress any key to continue or endkey to exit" , result);
} while (Console.ReadKey().Key != ConsoleKey.End);
Console.ReadLine();
}
static string LexicoGraphical(string inputData)
{
//hashset will keep track on passed char
var passedCharSet = new HashSet<char>();
// we can make use of stack LIFO behaviour to build result
var resultSet = new Stack<char>();
for (int index = inputData.Length - 1; index >= 0; index--)
{
var currentChar = inputData[index];
if (!passedCharSet.Contains(currentChar))
{
passedCharSet.Add(currentChar);
resultSet.Push(currentChar);
}
else if (currentChar < inputData[index+1])
{
// add char to stack & we can skip old position of char by ignoring it in 2nd pass
resultSet.Push(currentChar);
}
}
passedCharSet = new HashSet<char>();
var resultEnum = resultSet.GetEnumerator();
StringBuilder builder = new StringBuilder();
while (resultEnum.MoveNext())
{
//skip char who's index is changed in 1st pass
if (!passedCharSet.Contains(resultEnum.Current))
{
builder.Append(resultEnum.Current);
passedCharSet.Add(resultEnum.Current);
}
}
return builder.ToString();
}
Repsuejnagel, Virus Researcher at Email Customer Service
Hello, I am Sue . I am a chief information officer at Vernon. I am responsible for providing the global communications ...
Repmarthajpatton, Data Scientist at AppPerfect
Managed a small team implementing gravy in Prescott, AZ. Developed several new methods for easy break up spells.Had some ...
here is my C# version of solution. i think we can not build palindrome string if we get more than one char with odd occurrence
following will be steps to solve it
1 iterate string array and find char & it occurrence count
2 loop above dictionary & build string start part & end part . if we get more than one char having odd occurrence retrun -1
- paku September 14, 2015