Remove duplicate in a string

I am preparing for an interview technical test and I came across this question:

Remove all duplicates in a string without using a buffer, 1 or 2 additional variable is allowed.

I would like to know in doi开发者_如何学Pythonng the following, am I using a buffer? Thanks.

static void Main(string[] args)
{
    string temp = "amanisaman";
    temp = noDups(temp);
    MessageBox.Show(temp);
}

public string noDups(string word)
{
    string table = "";

    foreach (var character in word)
    {
        if (table.IndexOf(character) == -1)  
        {
            table += character; // would this count as a buffer storage?
        }
    }
    return table;
}

Using LINQ...

This assumes your temp string and you want to remove the characters.

string originalString = "amanisaman";
string newString = string.Join(" ", originalString.ToCharArray().Distinct());

This assumes that you want to remove duplicate words.

string originalString = "this is my test string here, this test";
string newString = string.Join(" ", originalString.Split(new Char[] {' '}).Distinct());
               

This is because if exists same char in your string,the index is forever same. Try this:

 static string noDups(string word)
        {
            string table = "";
            int pos = 0;
            foreach (var character in word.ToCharArray())
            {
                pos = table.IndexOf(character, Math.Abs(pos));
                if (pos == -1)
                {
                    table += character;
                }


            } 
            return table;

        }

I think that .IndexOf method for this is not idea good. You can use .Contains method or LINQ.

Using LINQ:

 string input = "abahehe";
 string output = new String(input.ToCharArray().Distinct().ToArray());

There are a number of errors in the code you posted (try compiling it!), but the following approach works by creating an extension method to the String class:

    static class Program
{
    static void Main(string[] args)
    {
        String temp = ("amanisaman");
        Console.WriteLine(temp.RemoveDupes());
        Console.ReadLine();
    }
    static String RemoveDupes(this String x)
    {
        return String.Join("", x.Distinct());
    }
}

Strings in C# are immutable. Therefore you have to allocate another memory location in some way, which is a buffer, unless you are going to go "unsafe".

This question may actually not be looking for a code answer as much as the correct answer, that in C#, this is not possible unless you go "unsafe".

O(n) solution:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

 void removeDuplicates(char *);

 void removeDuplicates(char *inp)
{
        int i=0, j=0, FLAG=0, repeat=0;

    while(inp[i]!='\0')
    {
            if(FLAG==1)
            {
                    inp[i-repeat]=inp[i];
            }
            if(j==(j | 1<<(inp[i]-'\0')))
            {
                    repeat++;
                    FLAG=1;
            }
                    j= j | 1<<(inp[i]-'\0');
                    i++;
    }

    inp[i-repeat]='\0';
}

 int main()
{
    char inp[100] = "aaAABCCDdefgccc";
    //char inp[100] = "ccccc";
    //char inp[100] = "\0";
    //char *inp = (char *)malloc(sizeof(char)*100);

    printf (" INPUT STRING : %s\n", inp);

    removeDuplicates(inp);

    printf (" OUTPUT STRING : %s:\n", inp);
    return 1;
}

Yes table is counted as a buffer.

I just want to mention that strings are immutable and any removing (or adding) will cause creation of new string which also could be considered as a buffer.

To minimize extra memory I would do the following:

string s = "ababagalamaga";
var h = new HashSet<char>(s);
var b = new StringBuilder();
foreach (char ch in h) {
    b.Append(ch);
}
Console.WriteLine(b);

"Without using a buffer" is a really bad requirement. What does it mean? Is a new string a buffer? Depending on the interpretation of this requirement, the assignment ranges from very easy to impossible in C#.