Determing if string has all unique characters

Question

How can I do this without using arrays? I have this implementation, but I need to do it without using arrays, bit operations and any other C/C++ libraries.

bool IsCharDuplication(string s) {
  bool result = false;
  bool controlArray[256];
  for (int i = 0; i < s.length(); i++) {
    int val = s[i];
    if (controlArray[val] == true) {
      result = true;
      break;
    }
    controlArray[val] = true;
  }
  return result;
}

Solution 1

Use two nested loop:

bool IsCharDuplication(string s)
{   
 for (int i = 0; i < s.length(); i++) 
    for (int j = i+1; j < s.length(); j++) 
      if (s[i] == s[j])
        return true;   
 return false;
}

Note: your algorithm has time of O(N), But my solution has time of O(N^2).

Solution 2

You can do better than the O(N^2) algorithm suggested in the other answer.

For example, you can Quick-sort or Merge-sort the String in O(NlogN) and than do a single pass over the sorted String to determine if there are any duplicates in O(N). There total time complexity will be O(NlogN).

bool IsCharDuplication (string s)
{
  string s2 = sort(s);
  for (int i = 0; i < s.length () - 1; i++)
    if (s2[i] == s2[i+1])
      return true;
  return false;
}

I didn't include the code for sorting the string, but you can find such code easily and write your own sort method (since you are not allowed to use C/C++ libraries).