CareerCup

use hashing. if a character is already present in the hash table, return false.

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));
//return 0;
}

}

I would use an array of size 256. An array is more efficient for ASCII.

To Jack: They didnt say if the chars were ascii so hash table is still a better choice.

Assuming you don't know the character-set beforehand...

There's a trade-off between using a HashSet and a HashTable.

HashTable:
Need to check if integer is already 1.

HashSet:
Need to check if node already exists by letting the data structure traverse, typically, a BST. Seems cleaner than using a hashtable but slower lookup. Seems more OO.

Take an array of size 65536 and init to all 0. It is kind of bucket or hash, directly use the char value as the index in array, new one set to 1. If already 1, false
The size of hash table will also need to be 65536, so ...

James,

Why would you use 65536 = 2^16 ?
Every ascii code list shows 255 = 2^8 values.

THX,
Eila

Eila - for Unicode which is 16-bit (at least the one commonly used)

A simple solutions using strchr and memset-

#include<stdio.h>

int main()
{
char str[' '], *ptr, ch;
int i=0, j;

printf("\nEnter a string: ");
scanf("%s",str);

while(str[i] != '\0')
{
ch = str[i];
ptr = strchr(str, ch);
memset(ptr, '0', sizeof(char));

// Look again if another instance of the char exists
ptr = strchr(str, ch);
if(ptr == NULL)
{
i++;
continue;
}
else
{
printf("\nString contains duplicate character (%c)!\n",c
h);
return;
}
}
printf("\nString contains unique elements\n\n");
}

A simple solutions using strchr and memset-

#include<stdio.h>

int main()
{
char str[' '], *ptr, ch;
int i=0, j;

printf("\nEnter a string: ");
scanf("%s",str);

while(str[i] != '\0')
{
ch = str[i];
ptr = strchr(str, ch);
memset(ptr, '0', sizeof(char));

// Look again if another instance of the char exists
ptr = strchr(str, ch);
if(ptr == NULL)
{
i++;
continue;
}
else
{
printf("\nString contains duplicate character (%c)!\n",c
h);
return;
}
}
printf("\nString contains unique elements\n\n");
}

Quicksort the string ( O(n log n) ) and sequential search from the beginning to the end for duplicates ( O (n) ).
So totally, O(n log n).

Quicksort O(nlogn) + linear search is O(n+nlogn)

Actually, quicksort is nlogn on avg, so it could be O(n^2)...

If storage isn't a concern, use dynamic programming to get a 0.5*c*n running time. Associate array or hashset will do. Search the string from the front and back using one iterator. Store each unique character. During search, do a lookup. Hence, the running time is O(n).

to make this in o(n) times you can use extra memory space.
Use the following approach:

take an extra array of 26 chars.
parse the string from left to right.
if it encounters
[a]; increment a[1]+1;
[b]; do a[2]+1;
.
.
..
.
.
[z]; do a[z]+1



if this new array contains 2 in any field. there is duplication.

Associate a prime number with each unique character
Find the product of all the prime numbers associated with the string.
Then for uniqueness divide the product by square of each of the prime numbers .
If it leads to zero remainder then there is repeatition of the character

I guess,
a single bit would be enough to hold the ture and false (in case the char is not found)

so you need only
32 bytes - ansi
8192 bytes - unicode

We can use STL bitset<N> for this purpose. where N is equal to 255 (if we have ascii) & 52 (if we have only alphabets. <br>

Here every bit will act like a boolean (true/false) for single character. Initially we will reset all bits. If we found 'a' in the string, we will set the bit equivalent its ascii value. If this char repeats again, we can identify it just be checking the corresponding bit in bitset.

Regards

what is hashset. How is it different from Hash Table.

You can use binary search tree.
O(n) insertions All taking a maximum of O(n square) time.. Size O(n).

Few comments on the disscusions so far:

1>Associating prime numbers is not a good idea 'coz finding huge set of prime numbers itself is a big task in term of runtime and memory offcourse.

2> If we dont have any extra memory then quick sort or any good in house sort will be a good idea with run time - bestcase(nLogn) and worstcase (n*n)

3>If extra memory if available, then using hashtable (or hashset based on language specific implementation) will be better choice than array of size 2^16. 'Coz array needs 2^16 memory anyway where as Hashtable-memory will grow as we process the string. If 2nd and 3rd characters are duplicate , hashtable uses only 2 memory spaces to discover it compared to array's huge fixed size of 2^16. Runtime of both is O(n)

4> Finally "hitesh1407"'s solution of using bits to indicate if a char is present in the string is a very good idea given the chances of the input string having duplicate is very less.

So if we know the input string is very prone to have duplicates - hashtable is a better choice, otherwise option <4> may turn out a good choice.

I feel that a bit vector representation would be the most efficient in terms of memory. Depending on the character set, use appropriate number of bits and as you read char by char, set the bits accordingly if it is not already set, in which case, the string doesn't contain unique characters.

Yup Lawn Mower is right....

void uniChar(char *uni){
	char temp[256] /// 2^16 if you want even for uni-code characters else 2^8 is enough

	for(int i=0;i<256;i++)
		temp[i]=0;
	i=0;
	while(uni[i]){
		if(temp[uni[1])==1)
			return false;
		else
			temp[uni[i]]=temp[uni[i]]+1;
			i++;
	}

	return true;
}

void uniChar(char *uni){
	Hashtable h=new Hastable();
	char c;
	int i=0;
	while(uni[i]){
		int temp=h.get(uni[i]);
		if(!temp)
			h.put(uni[i],1);
		else if(temp ==1)
			return false;
	}
	return true;
}

this is a simple qs...why to make it complex by using hi-fi stuffs....both teh solution from Vamshi are ok...

for i 0 to n {
idx = atoi(str[i])
if(tempStr[idx] != null) then not unique and return
else tempStr[idx] = str[i]
}
then unique and return

I'm assuming only one thing: The string is only with ASCII or UNICODE. No mixing.
This is not the most efficient algorithm, but:
Start building BST using the integer representation of the characters. In the process of building if you find a node with the same value this is duplication. This way I don't need to separate stack memory for all possible characters from any table. I can finish in the 5th iteration. In the worst case scenario I will have a tree that will contain all the allowed characters.
Thanks

Clarifications:
I mean with "I can finish on the 5th iteration." that it is possible to find almost immediately a duplicated value. According to

A bitset implementation will be the best approach.
As hitesh1407 describes.

O(n) time and O(1) space:
====================================
bool unique(char* input)
{
bool ascii[255];
for(char* i=input; *i!='\0'; i++){
if (ascii[*i]==true)
return false;
ascii[*i]=true;
}
return true;
}

hitesh1407 can yo say why we need only 32 bits ??? the bit vector

Here is a solution using bitvector (borrowed from k2code.blogspot.in/2014/03/determine-if-string-has-all-unique.html) :
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;
}

}

import java.util.*;
public class HashTables {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner n =new Scanner(System.in);
String s = n.nextLine();
Hashtable<Character,Integer> hs=new Hashtable<Character,Integer>();
Enumeration repeat;
int flag=0;
int p=0;
for(int i=0;i<s.length();i++)
{
for(int j=i+1;j<s.length();j++)
{
if(s.charAt(i) == s.charAt(j))
{
if(hs.isEmpty())
{
hs.put(s.charAt(i),p);
p++;
}
else
{
repeat = hs.keys();
while(repeat.hasMoreElements())
{
if(s.charAt(i) != (char)repeat.nextElement())
{
flag = 1;
}
else
{
flag = 0;
}
}
if(flag == 1)
{
hs.put(s.charAt(i), p);
p++;
}
}
}
}
}

System.out.println(hs);


n.close();
}
}

public boolean isUniqueChar(String str){
if(str.length() > 128) return false;

boolean charSet[] = new boolean[256];
for(int i =0 ; i<str.length();i++){
int val
}


}