determine if a string has all unique characters?

Question

Can anybody tell me how to implement a program to check a string contains all unique chars ?

Lissie

Answer 1

If you are talking about an ASCII string:

1. Create an int array [0-255], one for each character index, initialised to zero.

2. Loop through each character in the string and increment the respective array position for that character

3. If the array position already contains a 1, then that character has already been encountered. Result => Not unique.

4. If you reach the end of the string with no occurrence of (3), Result => the string is unique.

Palish

+1 I like this one the best! And in fact I've actually implemented this way, years ago. My memory must be going! – Madi

If you are talking about an ASCII string, array with 128 elements will do just fine. (Actually, in the case of C strings 127 elements would be enough, but less convenient.) – Russel

And if you are not talking about an ASCII string but a string of UTF-8 Unicode runes, then a hash-table approach along the same idea is probably going to be easy and fast to implement. Note also Ira Baxters solution with a Boolean array which has better space usage - for in-between sized data it may be valuable. – Gilmagilman

If you're talking about an ASCII string, welcome to the future! We may not have personal jetpacks yet, but we do have unicode! – Tridentine

This was actually given to me as an interview question. This was my answer, but my interviewer suggested that instead of an int array that it was possible to use an array of bits (or, to make it easier, chars or bytes) to save memory. Its O(1) to search the array if your indices are mapped from your char values! – Jehial

What if we don't get a new data structure? – Unusual

A good optimisation would be to check that the that the length of the string is less or equal to 256 (Assume extended ASCII is used), if the string is greater then return false immediately. The whole idea here is that you cannot have a string with 300 characters when only 256 unique characters are available. The time complexity for this code is O(n) and the space complexity is O(1) – Inharmonic

Answer 2

Sort the characters in the string using your algorithm of choice (e.g. the builtin qsort function), then scan the string checking for consecutive repeating letters; if you get to the end without finding any, the string contains all unique characters.

An alternative may be using some structure that has one bucket for each character the string may contain, all initialized to zero; you scan the string, incrementing the value of the bucket corresponding to the current character. If you get to increment a bucket that already has a 1 inside it you are sure that your string contains duplicates.

This can work fine with chars and an array (of size UCHAR_MAX+1), but it quickly gets out of hand when you start to deal with wide characters. In such case you would need a hashtable or some other "serious" container.

The best algorithm depends on the length of the strings to examine, the size of each character, the speed of the sorting algorithm and the cost of allocating/using the structure to hold the character frequencies.

Wollis

This qsort idea is neat because it uses an already built-in function. An alternative on the idea is to store elements in a tree (a set) and bail when a new character is already a set-member. Thus you avoid the extra work of having to sort the whole array, even if it is the string 'aa..' you are asking on. – Gilmagilman

why I always get true for using this sort solution? public static boolean uniqueCharacters(String s){ Arrays.sort(s.toCharArray()); for(int i = 1; i < s.length(); i++){ if(s.charAt(i) == s.charAt(i-1)){ return false; } } return true; } – Shadowgraph

Even this one is not working: public static boolean uniqueCharacters(String s){ Arrays.sort(s.toCharArray()); String sorted = new String(s); for(int i = 1; i < sorted.length(); i++){ if(sorted.charAt(i) == sorted.charAt(i-1)){ return false; } } return true; } could you please have a look, and see what is wrong? Thanks – Shadowgraph

@Shadowgraph : you are not keeping the char[] from (non-standard) s.toCharArray() - it gets lost after sorting. Comparing consecutive chars from a copy of the original String is as useless as is operating on the latter. – Rinehart

Answer 3

Make a set of the letters, and count the values.

set("adoihgoiaheg") = set(['a', 'e', 'd', 'g', 'i', 'h', 'o']):

def hasUniqueLetters(str):
    return (len(set(str)) == len(str))

>>> hasUniqueLetters("adoihgoiaheg")
False

Studdard

Answer 4

#include <iostream>
#include <string>
using namespace std;

bool isUnique(string _str)
{
        bool char_set[256];
        int len = _str.length();

        memset(char_set, '\0', 256);
        for(int i = 0; i < len; ++i)
        {
            int val = _str[i]- '0';
            if(char_set[val])
            {
                return false;
            }
            char_set[val] = true;
        }

        return true;
    }

    int main()
    {
        cout<<"Value: "<<isUnique("abcd")<<endl;
        return 0;
    }

Bisque

@Orbling: Yes, shouldn't it be - 'a' ? – Erudition

@krishnang: The point of using a flag array with a size of 256, is that it represents every possible value of an 8-bit character string. There is therefore no need at all to subtract anything from the value of each character, as all that would achieve here is making negative index values for any character below the subtracted ordinal value, which would be an out-of-bounds index for the array and crash the program. – Dumpish

@krishnang: In the case of the code above using '0', that would result in all characters below 48 crashing the code (like space and a deal of punctuation). Using 'a' instead would move that up to 97, making all uppercase characters and digits cause an error. – Dumpish

The question is tagged C. This answer is C++. If you're going to insist on a C++ answer, at least use the functions from <algorithm>. – Dagda

Answer 5

Use a 256-entry array. Fill it with 0. Now traverse the string setting the corresponding entry in the array to 1 if it's 0. Otherwise, there are repeated chars in the string.

Escarole

Answer 6

Set an array of booleans of size equal to the character set to false. (Constant time). Scan the string; for each character, inspect the array at the characater's slot; if true, string has duplicate characters. If false, set that slot to true and continue. If you get to the end without encountering a duplicate, there aren't any and the string only contains unique characters. Running time: O(n) when n is the lenght of the string, with a pretty small constant.

Nannana

Answer 7

Similarly (and without arrays), use a HASH TABLE!

//psuedo code:

1. go through each char of the string
2. hash the char and look it up in the hash table
3. if the table has the hash, return FALSE // since it's not unique
4. __else store the hash
5. return to step #1 until you're done

Run time is O(n) and memory space is better too since you don't need an array of 256 (asciis)

Amateur

Depends on hashtable implementation. Hashtable might initialize to a size of 256. – Walkway

Answer 8

#include <stdio.h>

#define ARR_SIZE 32

unsigned char charFlag[ARR_SIZE];

void initFlag() {
    int i = 0;

    for (i = 0; i < ARR_SIZE; i++)
        charFlag[i] = 0;

}

int getFlag(int position) {
    int val = 0;
    int flagMask = 1;

    int byteIndex = position / 8;
    int locPos = position % 8;

    flagMask = flagMask << locPos;
//  flagMask = ~flagMask;

    val = charFlag[byteIndex] & flagMask;
    val = !(!val);
//  printf("\nhex: %x\n", val);
    return val;

}

void setFlag(int position) {
    int flagMask = 1;
    int byteIndex = position / 8;
    int locPos = position % 8;

    flagMask = flagMask << locPos;
    charFlag[byteIndex] = charFlag[byteIndex] | flagMask;

}
int isUniq(char *str) {
    int is_uniq = 1;

    do {
        char *lStr = str;
        int strLen = 0;
        int i;

        if (str == 0)
            break;

        while (*lStr != 0) {
            lStr++;
            strLen++;
        }

        initFlag();
        lStr = str;
        for (i = 0; i < strLen; i++) {
            if (getFlag(lStr[i]))
                break;

            setFlag(lStr[i]);
        }

        if (i != strLen)
            is_uniq = 0;

    } while (0);

    return is_uniq;
}

int main() {

    char *p = "abcdefe";
    printf("Uniq: %d\n", isUniq(p));
    return 0;
}

Rondure

Answer 9

Use a HashTable, add the key for each character along with the count of occurrences as the value. Loop through the HashTable keys to see if you encountered a count > 1. If so, output false.

Standby

a hash table is too expensive for this purpose. A simple table would be fine, unless you want to work with arbitrary Unicode strings – Emotionality

Answer 10

Simple solution will be using 2 loops. No additional data structure is needed to keep a track on characters.

bool has_unique_char(char *str,int n)
{
      if(n==0)
           return true;

      for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                    if(str[i] == str[j])
                          return false;
            }      
      }
      return true;
}

Ame

but this is O(n²) instead of O(n) like other answers – Emotionality

Answer 11

bool isUnique(char st[],int size)
{
    bool char_set[256]=false;
    for(int i=0;i<size;i++)
    {
        if(char_set[st[i]]-'0')
        return false;
        char_set[st[i]-'0')=true;
    }
    return true;
}

Hollington

Answer 12

my original answer was also doing the similar array technique and count the character occurrence.

but i was doing it in C and I think it can be simple using some pointer manipulation and get rid of the array totally

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

void main (int argc, char *argv[])
{
    char *string;
    if (argc<2)
    {
        printf ("please specify a string parameter.\n");
        exit (0);       
    }

    string = argv[1];
    int i;

    int is_unique = 1;
    char *to_check;
    while (*string)
    {
        to_check = string+1;
        while (*to_check)
        {
            //printf ("s = %c, c = %c\n", *string, *to_check);
            if (*to_check == *string)
            {
                is_unique = 0;
                break;
            }
            to_check++;
        }
        string++;
    }

    if (is_unique)
        printf ("string is unique\n");
    else
        printf ("string is NOT unique\n");
}

Upsetting

so this is O(n²) which is worse than most answers here which is O(n), and it's less readable than other O(n²) answers – Emotionality

Answer 13

Without using additional memory:

#define UNIQUE_ARRAY 1
int isUniqueArray(char* string){
    if(NULL == string ) return ! UNIQUE_ARRAY;
    char* current = string;
    while(*current){
        char* next   = current+1;
        while(*next){
            if(*next == *current){
                return ! UNIQUE_ARRAY;
            }
            next++;
        }
        current++;
    }
    return UNIQUE_ARRAY;
}

Anhydrite

This seems to be a partial answer only: the question being Can anybody tell […] ?, you didn't. – Rinehart

this is using pointers exactly the same as ledmirage's answer, and both are O(n²) – Emotionality

Answer 14

I beleive there is a much simpler way:

int check_string_unique(char *str) 
{
   int i = 0;
   int a = 0;
   while (str[i])
   {
      a = i + 1; // peak to the next character
      while (str[a])
      {
          if (str[i] == str[a]) // you found a match
             return (0); // false
          a++; // if you've checked a character before, there's no need to start at the beggining of the string each time. You only have to check with what is left.
      }
   i++; //check each character.
   }
return (1); //true!
}

Zito

this is O(n²) which is a lot worse than other solutions – Emotionality

Answer 15

I hope this can help you

#include <iostream>
using namespace std;
int main() {
 string s;
 cin>>s;
 int a[256]={0};
 int sum=0;
 for (int i = 0; i < s.length();i++){
    if(a[s[i]]==0)++sum;
    a[s[i]]+=1;
 }
 cout<<(sum==s.length()?"yes":"no");
 return 0;

}

Franchescafranchise

Answer 16

this is optimal solution for the problem. it takes only an integer variable and can tell whether it is unique or not regardless of string size.

complexity

best case O(1)

worst case O(n)

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - ‘a’;
        if ((checker & (1 << val)) > 0) 
            return false;
        checker |= (1 << val);
    }
    return true;
}

Lustful