String unique characters

Question

Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

Answer 1

If you can use a little auxiliary memory, then a small array of bits (indexed by the numerical code of the character) is all you need (if your characters are 4-byte Unicode ones you'll probably want a hashmap instead;-). Start with all bits at 0: scan the string from the start -- each time, you've found a duplicate if the bit corresponding to the current character is already 1 -- otherwise, no duplicates yet, set that bit to 1. This is O(N).

If you can't allocate any extra memory, but can alter the string, sorting the string then doing a pass to check for adjacent duplicates is the best you can do, O(N log N).

If you can't allocate extra memory and cannot alter the string, you need an O(N squared) check where each character is checked vs all the following ones.

Answer 2

answer in c program

int is_uniq(char *str) 
{
    int i = 0, flag = 0, value = 0;
    for(i = 0; i < strlen(str); i++) {
        value = str[i] - 'a';
        if(flag & (1 << value)) {
            return 0;
        }
        flag |= (1 << value);
    }
    return 1;
}

Answer 3

we can do it by assigning a prime number to every character.. and multiply it for every character found. then on every character check that if the value is divisible by the number assigned to that character or not..

Answer 4

for each character in the string
  if any subsequent character matches it
    fail
succeed

Answer 5

import java.io.*;

public class uniqueChar
{
    boolean checkUniqueChar(String strin)
    {
        int m;
        char []str=strin.toCharArray();
        java.util.Arrays.sort(str);
        for(int i=0;i<str.length-1;i++)
        {
            if(str[i]==str[i+1])
                 return false;
        }
        return true;
    }

    public static void  main(String argv[]) throws IOException 
    {
        String str;
        System.out.println("enter the string\n");
        InputStreamReader in=new InputStreamReader(System.in);
        BufferedReader bin=new BufferedReader(in);
        str=bin.readLine();
        System.out.println(new uniqueChar().checkUniqueChar(str));
    }
}

Answer 6

the prime method described by partik (based on this theorem). It's O(N).

# one prime per letter
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

starting_byte = ?a.ord
primes_product = 1

ARGV[0].each_byte do |byte|
    current_prime = primes[byte - starting_byte]
    if primes_product % current_prime == 0
        puts "Not unique"
        exit 
    else
        primes_product = primes_product * current_prime
    end
end

puts "Unique"

Answer 7

I came on this thread for the similar question and ended up with the following solution in C#:

        var data = "ABCDEFGADFGHETFASAJUTE";

        var hash = new Dictionary<char, int>();

        foreach (char c in data)
        {
            if (hash.ContainsKey(c))
            {
                hash[c] += 1;
            }
            else
            {
                hash.Add(c, 1);
            }
        }

        var Characters = hash.Keys.ToArray();
        var Frequencies = hash.Values.ToArray();

Answer 8

One possible solution - You could extract the string into an array of characters, sort the array, and then loop over it, checking to see if the next character is equal to the current one.

Answer 9

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