Check string for duplicate char

Question

The first time I write in SO, because he could not find a solution on his own. At the interview, I was given the task of writing a method that checks the characters in a string for a unique one.

Requirements: do not use LINQ . Preferred: do not use additional data types (dictionary, HashSet ... etc. Arrays and lists Valid )

Example:

"Hello" - return false; "Helo" - return true 

My implementation:

 static HashSet<char> charSet = new HashSet<char>(); static bool IsUniqueChar(string str) { foreach (char c in str) { charSet.Add(c); } return charSet.Count() == str.Length; } 

But it does not meet the requirements of data types and is not the best performance ... I also tried a dictionary approach:

 static Dictionary<char,bool> charSetDictionary = new Dictionary<char,bool>(); static bool IsUniqueChar(string str) { try { foreach (char c in str) { charSetDictionary.Add(c,true); } } catch { return false; } 

But he is not better than the previous one. I will welcome any idea how best to solve this problem? ps

 static void Main(string[] args) { Stopwatch sw = Stopwatch.StartNew(); IsUniqueChar("Hello"); sw.Stop(); Console.WriteLine("Elapsed={0}", sw.Elapsed); //~005044 } 

Answer 1

Most likely, your interviewer would like to see an approach using knowledge of Unicode:

 static bool[] charsHash = new bool[512]; static bool IsUniqueChar(string str) { if (str.Length > 512) return false; foreach (char c in str) { bool alreadyExist = charsHash[(int)c]; if (alreadyExist) return false; else charsHash[(int)c] = !alreadyExist; } return true; } static void Main(string[] args) { Stopwatch sw = Stopwatch.StartNew(); IsUniqueChar("Hello"); sw.Stop(); Console.WriteLine("Elapsed={0}", sw.Elapsed);//~000283 } 

Answer 2

The fastest way uses a HashSet<char> :

 var set = new HashSet<char>(); foreach(var c in input) { if(!set.Add(c)) return false; } return true; 

O (n) solution in the worst case (input is unique). Returns false as soon as the first duplicate is found.

Without a HashSet<char> you can easily convert string to char[] , sort it, and check if you have two consecutive elements with the same value.

 var chars = input.ToCharArray(); chars.Sort(); for(int i = 1; i < chars.Length; i++) { if(chars[i-1] == chars[i]) return false; } return true; 

Sort is O (n log (n)), which means the whole function.

Answer 3

All answers so far are based on the assumption that one .NET char matches one Unicode character. This is true only for characters in the Basic Multilingual Plane . Characters outside the BMP are encoded using two char objects (surrogate pair).

The following code handles this special case:

 HashSet<string> set = new HashSet<string>(); for (int i = 0; i < str.Length; i++) { string s; if (char.IsHighSurrogate(str[i])) { s = str.Substring(i, 2); i++; } else { s = str.Substring(i, 1); } if (!set.Add(s)) { return false; } } return true; 

Answer 4

Suppose the test string is passed through textBox1 , and then:

 string tst; int i,j, stat =0; tst = textBox1.Text; for (i = 0; i < tst.Length; i++) { for (j = 0; j < tst.Length; j++) { if ((tst[i] == tst[j]) && (i != j)) { stat = 1; break; } else continue; } if (stat == 1) break; else continue; } if (stat == 1) MessageBox.Show("False"); else MessageBox.Show("True"); 

Each line is an array of characters.