how to find even duplicates character in a string in C# .Net

user_10519551 0
Viewed 300

I have a question of how to remove even duplicates in a string in C#.

example - input string:

acdhqodcqasaf

output:

acdhqosaf

What I really mean is to remove even occurrences of characters.I have written the logic but I have used nested for loops and its efficiency is O(n^2) which is not good efficiency.So I was asked to do in different way searched online still did not get the answer

string .net c#
5 Answers

You could use a dictionary to track the number of occurences and use the % operator:

string input = "acdhqodcqasaf";
var charOccurences = new Dictionary<char, int>();
int removeEvery = 2;
var outputBuilder = new StringBuilder();

foreach (char c in input)
{
    charOccurences.TryGetValue(c, out int charOccurence);
    charOccurence++;
    charOccurences[c] = charOccurence;
    if (charOccurence % removeEvery != 0)
        outputBuilder.Append(c);
}

string output = outputBuilder.ToString();
user_2842400

I'd use a HashSet to keep track of which characters you've seen an odd number of times.

string input = "acdhqodcqasaf";
var oddOccurrences = new HashSet<char>();
var output = new StringBuilder();
foreach (var c in input)
{
    if (!oddOccurrences.Contains(c))
    {
        output.Append(c);
        oddOccurrences.Add(c);
    }
    else
    {
        oddOccurrences.Remove(c);
    }
}
Console.WriteLine(output.ToString());
user_1209550

Create a bool[], that keeps track of odd and even for you:

bool[] even = new bool[256];
string input = "acdhqodcqasaf";
string output = "";
for(int i=0;i<input.Length;i++)
{
    int x = (int)input[i];
    if(!even[x])output += input[i];
    even[x] = !even[x];
}

change bool[256] to bool[256*256], for 16-bit char support.

Live Demo

user_10792210

You can traverse the array, keep a dictionary<char,int> to keep count of each character. Check the count to see if you should delete the char or not add it in a result string.

user_6932720

Just for fun and giggles I've stopwatched the top answers for this question and added a Distinct method:

return new string(input.Distinct().ToArray());

The output was interesting (10k runs):

ASDHFAJSHKDFASJDFHJgasdfkjhasdjhfashdfkjasdjkfajkhewkjrhwakhfuiwhfsdnfvjndfsjkgnklwerjliu4596945
Distinct 344
RunForEach1 551
RunForEach2 522
RunFor 454

When running 10k times distinct seems to win (in speed) although when running 100 times the result is quite different:

ASDHFAJSHKDFASJDFHJgasdfkjhasdjhfashdfkjasdjkfajkhewkjrhwakhfuiwhfsdnfvjndfsjkgnk
Distinct 9
RunForEach1 7
RunForEach2 1
RunFor 1

Code:

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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var sw = new System.Diagnostics.Stopwatch();

            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                RunDistinct(input);
            }
            sw.Stop();
            Console.WriteLine($"Distinct {sw.ElapsedMilliseconds}");

            sw.Reset();
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                RunForEach1(input);
            }
            sw.Stop();
            Console.WriteLine($"RunForEach1 {sw.ElapsedMilliseconds}");

            sw.Reset();
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                RunForEach2(input);
            }
            sw.Stop();
            Console.WriteLine($"RunForEach2 {sw.ElapsedMilliseconds}");

            sw.Reset();
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                RunFor(input);
            }
            sw.Stop();
            Console.WriteLine($"RunFor {sw.ElapsedMilliseconds}");

            Console.ReadKey();
        }


        private static string RunDistinct(string input) {
            return new string(input.Distinct().ToArray());
        }

        private static string RunForEach1(string input) {
            var charOccurences = new Dictionary<char, int>();
            int removeEvery = 2;
            var outputBuilder = new StringBuilder();

            foreach (char c in input)
            {
                charOccurences.TryGetValue(c, out int charOccurence);
                charOccurence++;
                charOccurences[c] = charOccurence;
                if (charOccurence % removeEvery != 0)
                    outputBuilder.Append(c);
            }

            return outputBuilder.ToString();
        }

        private static string RunForEach2(string input)
        {
            var oddOccurrences = new HashSet<char>();
            var output = new StringBuilder();
            foreach (var c in input)
            {
                if (!oddOccurrences.Contains(c))
                {
                    output.Append(c);
                    oddOccurrences.Add(c);
                }
                else
                {
                    oddOccurrences.Remove(c);
                }
            }
            return output.ToString();
        }

        private static string RunFor(string input)
        {
            bool[] even = new bool[256];
            string output = "";
            for (int i = 0; i < input.Length; i++)
            {
                int x = (int)input[i];
                if (!even[x]) output += input[i];
                even[x] = !even[x];
            }

            return output;
        }
    }
}
user_1684250
Related