CareerCup

1) In java we can create a Hash<String, int> where int will be the count(though we do not need that) Later we can find out the length of the hash. It will work for java.

2) In case of C we can use trie to implement this.

Please let me know if there is any better solution than the above.

Hashing would be best approach for O(n).
n = length of array.
Before inserting each element to hash table look for if found n-- otherwise insert to table.
return n

is it array of Strings??
we can solve it in many ways..can you give the complexity of the soln?

Copy each element of the array into std::set. Size of set = number of unique elements!
complexity = O(n)

TRIE IS good option. but only probelm it wastes so much of space.

step1: scan all strings and construct trie.
step2 : do Trie traversal, find unique string counts.


TC O(n)
SC O(n)

Trie is a good option, but proper approach would be cluster the strings with size as a perameter, then using a trie.

Hash option is good - with the caveat that a good hashing function is used with very low probability of collision. Also note that the strings themselves don't need to be inserted into the hash table, we only need to generate the keys.

I'm thinking to use hashMap in java, each char element in the string as a key. Only put the item into the table when it's the first time to find the key. Then the size of the items will be the number of distinct element. Please correct me if anything is wrong. thanks!

public int distinct_element(String str){
			HashMap<Character, Boolean> map=new HashMap<Character, Boolean>();
			for(int i=0;i<str.length();i++){
				char value=str.charAt(i);
				if(map.containsKey(value)==false){
					map.put(value, true);
				}
			}
			return map.size();
		}

How could it be o(n)? say string 12345, it will have 5 * (5 + 1) /2 node, that means if you count one by one, it takes n**2 / 2 steps. it is o(n**2).

can someone please elaborate the question??

So,

I could read the 2 possible solutions:
1) By Hash Table: Which is straight Forward. We just need to come up with a good Hash Function
2) Build TRIE.

Is there any other good solutions?

Thanks

Use the first step of KMP.

For example, given a string "abab", the number of substrings is 4 * 5 / 2 = 10

Compute the next array, we got A= [-1 , -1 , 0 , 1]. This array implies the redundancies of the string. For example, A[2] = 0, we know that s[2] = s[0], there are one redundant substring. A[3] = 1, we know that s[2, 3] = s[0,1] and s[3] = s[1], there are two redundant substrings.

So the result is: n(n + 1) / 2 - SUM(A[i] + 1) i from 0 to n

Complexity: O(n)

Use a suffix array and calculate the longest common prefix for the adjacent strings in the array.
Total no. of substrings = n*(n+1)/2

Now find the sum of all LCP for the suffix array.

No. of distinct substrings = Total no. of substrings - sum of all LCP

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>

using namespace std;

int pstrcmp(const void* p, const void* q)
{
    return strcmp(*(const char**)p, *(const char**)q);
}


 int lcp(char *p, char *q)
{
	int   len = 0;

	while(*p!='\0' && *p == *q){
		len++;
		p++;
		q++;
	}

	return len;

}


int main()
{
	char s[100];

	printf("Enter string:\n");
	scanf("%s",&s);

	int len;

	len = strlen(s);

	char *a[len];


	//Assign the suffix
	for(int i=0;i<len;i++)
		a[i] = &s[i];
	
	//Sort the suffix array
	qsort(a,len,sizeof(char *),pstrcmp);

	int sum = 0;

	for(int i = 0;i<len-1;i++){

		int   l;

		l = lcp(a[i],a[i+1]);	
		sum = sum + l;
	}

	int  res;

	res = (len * (len+1))/2;

	res = res - sum;

	printf("%d\n",res);

	

	return 0;

}

Different solutions:

a) Sort the array of strings
b) Put each string in a Set
c) Put each string in a HashMap
d) Construct a Trie from array of strings.

Could anyone tell me if my solution is O(n)?

std::vector<std::string> strings;
	
	strings.push_back("hola");
	strings.push_back("adeu");
	strings.push_back("heli");
	strings.push_back("caca");
	strings.push_back("caca");
	strings.push_back("pedo");
	strings.push_back("heli");
	strings.push_back("adeu");
	strings.push_back("hola");

	std::unordered_set<std::string> set;

	for (unsigned int k = 0; k < strings.size(); ++k)
	{
		std::string string = strings.at(k);
		set.insert(string);
	}

	int count = set.size();

Below is my Java code for this problem:
I used a HashMap. I would ask the interview does Capitalization matter? (Ex. Is Cat the same as CaT?)
If Capitalization matters, use the code below. If not, add
eachString = eachString.toLowerCase(); to the for loop.

public static int distinctString ( String [] inputArray){

			Map <String, Integer > hashMapOfString = new HashMap <String, Integer > ();
			
			int distinctCount =0;

			for ( String eachString : inputArray){

				      if ( ! hashMapOfString.containsKey(eachString) ){
					hashMapOfString.put(eachString,1);
					distinctCount++;	
				}

			}


			return distinctCount;
		}

In Java , we can use a HashSet. Add a string to the HashSet, if it returns false, which means the String is already present there, then remove that element from the HashSet. The resultant HashSet will contain all the distinct Strings.