CODEWITHSUNDEEP
calgorithmstringunique
Vishwanath Dalvi
Vishwanath Dalvi

Reputation: 36651

determine if a string has all unique characters?

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

Upvotes: 14

Views: 29098

Answers (16)

BlackHawk
BlackHawk

Reputation: 39

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;
}

Upvotes: 0

ANK
ANK

Reputation: 595

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;
}

Upvotes: 1

ayush saluja
ayush saluja

Reputation: 7

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;

}

Upvotes: 0

theVinDieselofRails
theVinDieselofRails

Reputation: 76

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!
}

Upvotes: 0

Madhu S. Kapoor
Madhu S. Kapoor

Reputation: 345

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;
}

Upvotes: 0

ledmirage
ledmirage

Reputation: 309

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");
}

Upvotes: 0

Sumit Gaur
Sumit Gaur

Reputation: 1

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;
}

Upvotes: 0

user2744865
user2744865

Reputation: 11

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.

Upvotes: 1

asterix
asterix

Reputation: 11

#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;
}

Upvotes: 1

user673558
user673558

Reputation: 61

#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;
    }

Upvotes: 6

Matthew
Matthew

Reputation: 2135

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)

Upvotes: 2

Phil H
Phil H

Reputation: 20151

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

Upvotes: 6

Matteo Italia
Matteo Italia

Reputation: 126867

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.

Upvotes: 7

Ira Baxter
Ira Baxter

Reputation: 95392

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.

Upvotes: 2

lhf
lhf

Reputation: 72352

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.

Upvotes: 3

mrcrowl
mrcrowl

Reputation: 1477

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.

Upvotes: 41

Related Questions