3
\$\begingroup\$

I am implementing the said question on "Cracking the Coding interview" using HashSet. Please have a look and suggest how I can improve the efficiency of the following code considering that I am only taking either all lower case or upper case characters.

static void detrUniqChar(String str)
{
 int flag = 0; //Flag declared here
 Set<Character> hashSet = new HashSet<Character>();

 for(char c : str.toCharArray())
 {
   if(c != ' ')
    {
     if(!hashSet.add(c))
      {
       System.out.println("Not unique " + c  );
       flag = 0;
       break;
      } 
     else { 
       flag = 1; 
      }
    }
  }
if(flag ==1 )System.out.println("Unique characters");
}

Does the space and time efficiency of this code equal to bitwise operation as per the solution provided by the book. As in solution worse case will be when the common elements are at first and last position of the string.

The code given in "Cracking the coding interview" is as follows:

public static boolean isUniqueChars(String str) {
if (str.length() > 256) {
    return false;
}
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;
}
\$\endgroup\$
5
\$\begingroup\$

The time complexity of both solutions is linear, proportional to the length of the input.

The space complexity of the solution in the book is constant, it uses a single integer regardless of the length of the input.

The space complexity of your solution is linear, it uses extra storage proportional to the size of the input. This is largely due to the str.toCharArray() call, which will result in an array the same size as the length of the input.

You could remedy that, by changing to a counting loop and using .charAt to access the characters. With that simple change, your space complexity becomes constant too, due to the finite size of the alphabet. However, you will still use more space than the book's solution, due to the set.

Your solution has several pretty grave mistakes:

  • printing instead of functions returning values
  • using an int with values 0 and 1 instead of a proper boolean
  • using a flag variable, when it's not necessary at all
  • strange, non-standard formatting
\$\endgroup\$
  • \$\begingroup\$ Thank you for the advice. Yes it's just a first iteration of my solution so I just wrote whatever came to my mind. \$\endgroup\$ – Himanshu Verma Dec 12 '15 at 22:48
  • 2
    \$\begingroup\$ You will get more out of this site by writing the very best code you can do. \$\endgroup\$ – Stop ongoing harm to Monica Dec 12 '15 at 22:50
  • \$\begingroup\$ Ok. I will try to implement it from next time. \$\endgroup\$ – Himanshu Verma Dec 12 '15 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.