The program finds the first non repeating character in a character array, array contains only small case letters.

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
char a2z[26]={0};//Hash

char input[100] = "abcbbbcdegh";//sample input, only small case english alphabets
int n = strlen(input);

for(int i=0; i<n; ++i)
{
    if( a2z[  input[i]-97 ]<0 )
    {
         //do nothing, this character has already repeated
    }
    else if( a2z[  input[i]-97 ]==0 )
    {
        a2z[ input[i]-97 ] = i+1; //character encoutered first time
    }
    else
    {
        a2z[ input[i]-97 ] = -(i+1); //repeating character
    }
}

int minAt=n+1;
for(int i=0; i<26; ++i) //finding first non-negative character in the Hash
{
    if( (a2z[i]>0) && (a2z[i]<minAt) )
    {
        minAt=a2z[i];
    }
}

if( minAt == n+1 )
    cout<<"\n\n no unique character";
else
    cout<<"\n\nFirst unique character is "<<input[minAt-1]<<" at position "<<minAt-1<<endl; 
}  

output ::

First unique character is a at position 0

here, i have taken an character array (i.e. a2z) of 26 characters initialized with zero, using it as Hash.
if a2z[i] is zero means ith character (of English alphabet) has not encountered till now, postive value of a2z[i] denotes ith character has been encountered only once at position a2z[i]-1, and negative values shows it has repeated.
pls review this code.

  • Add the output of the program too. It makes it easier for people without access to a compiler right now to look at your code. – rahul Jun 8 '12 at 6:13
  • @blufox added the output. – Eight Jun 8 '12 at 6:16
  • Are you looking for coding style tips, or trying to optimize for speed? – Corbin Jun 8 '12 at 7:31
  • @Corbin mainly coding style tips,but getting speed optimizations tips too would be great. – Eight Jun 8 '12 at 7:33
up vote 2 down vote accepted

As far as this program goes, there's not very many non-opinion improvements possible.

There are, however, a few correctness/(micro) optimization points:


char a2z[26]

A char is likely not big enough.

a2z[ input[i]-97 ] = i+1;
a2z[ input[i]-97 ] = -(i+1);

i = 0 ... strlen(input)-1 therefore min(i) = 0 and max(i) = strlen(input).

A signed char, c, can be: -128 <= c <= 127, therefore, your implementation is limited to strlen(input) <= 127.

Implicit Double Looping

Typically strlen() is implemented vaguely like:

size_t strlen(const char* str)
{
    size_t len = 0;
    while (str[len] != 0) {
        ++len;
    }
    return len;
}

Thus your program is looping over the string twice.

You could change your loop to basically embed the strlen in your code:

for(int i=0, const char* c = input; c != 0; ++i, ++c) {

That could be written a bit more cleanly, but hopefully it gets the point across.

(It also is probably not a very meaningful optimization. It likely would have equal, or depending on exactly how the loop is done, potentially worse performance. Just something to consider if you're trying to micro-optimize.)


Style oddities (blatant opinion with no backing)

These are a few items that are completely arbitrary in terms of correctness (basically all personal preferences):

  • It's valid, but for the sake of explicitness, I prefer to use the
    long form of main() and always include a return.
  • I also prefer to always use braces around the expressions for if and else statements. It's entirely a personal preference, but I've found that it tends to produces clearer, less error prone code
  • #include<iostream> I don't actually know if it's valid to not have a space between include and the file. Either way, I very rarely see it written like that, and it looks a bit odd.
  • a2z[ input[i]-97 ] looks a bit odd to me.
  • char input[100] = "abcbbbcdegh"; could be const char input[] = "abcbbbcdegh";
  • You complexity is wrong. Its O(n) as the loops are not nested. – Martin York Jun 8 '12 at 10:08
  • Oh you're right! Would be 2n which is still O(n). Thanks. Will edit it once I'm on a computer and not my phone. – Corbin Jun 8 '12 at 22:35

This is a bad habbit stop doing it.

using namespace std;

Once your programs are more than 10 lines long it starts adding complexity including the whole namespace. SO best not to do it. Get into the habit of not using now otherwise breaking the habit is hard latter.

Don't put bad comments in you code (in fact try not to put comments). A comment should explain what you are trying to achieve (or potentially why) (NOT HOW). The code explains how so don't duplicate the code in comments. The worst thing to find in code is comments that don't match the code.

char a2z[26]={0};//Hash

This is not a hash. A hash has a very specific meaning and this is not what you are doing.

Prefer to use [] when declaring the array. This means the compiler will try and establish the length of the array for you.

char input[100] = "abcbbbcdegh";//sample input, only small case english alphabets

While we are here. Stop using C stuff in C++. Learn to use C++ constructs and don't mix the languages up. Another bad habbit you should fall into.

int n = strlen(input);

C++ has its own string class.

std::string  input("abcbbbddddd");
// size is input.size()

Learn how to use iterators.

for(int i=0; i<n; ++i)

It will allow you to be more versatile with your code. Potentially allowing your code to work with multiple container types (not just string). But more importantly it is the first step to using the standard algorithms.

You are making the assumption that your input only contains lower case letters. You should always code defensively. You MUST validate your input.

  • 1
    "habit" not "habbit" :P Couldn't resist. – Casey Jun 8 '12 at 16:03
  • 1
    @Casey: The normal way to say that is s/habbit/habit/ We are comp sci people here and understand how to write things succinctly without ambiguity. – Martin York Jun 8 '12 at 23:28

The same program with a few changes. first, try to refactor your functions so that they are small, second, Often, using a case statement is more clearer to using cascading ifs. third, 'using namespace std' is a bad habit. It is probably ok to use in a small one off program like this, but avoid polluting your global namespace in larger projects. And avoid magic numbers when possible

#include<iostream>

char a2z[26]={0};

int process(char* input, int len) {
  for (int i=0; i<len; i++) {
    int c = input[i] - 'a';
    switch(a2z[c]) {
      case -1:
        continue;
      case 0:
        a2z[c] = i+1;
        break;
      default:
        a2z[c] = -1;
    }
  }
}

int findfirst(int min) {
  for(int i=0; i< sizeof(a2z); ++i) {
    if( a2z[i]>0 && a2z[i]<min ) min = a2z[i];
  }
  return min;
}

int main() {
  char input[] = "aabbbcbbbcddegghh";
  int n = sizeof(input);
  process(input, n);
  int minAt = findfirst(n+1);

  if( minAt > n )
    std::cout<<"no unique character"<<std::endl;
  else
    std::cout<<"First unique character is "
      <<input[minAt-1]
      <<" at position "<<minAt-1<<std::endl; 
}
  • Globals are almost always bad. – Corbin Jun 8 '12 at 8:07
  • Almost always :), here though, it may be an overkill to carry the hash around. – rahul Jun 8 '12 at 8:12
  • It would be 26 extra bytes, or an extra parameter. Seems worth it for thread safety and better encapsulation. (I'm likely being a bit overly picky, but it's a code review site.) – Corbin Jun 8 '12 at 8:14
  • agreed. I will update my answer accordingly. – rahul Jun 8 '12 at 8:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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