CareerCup

for(int c=0;c<str.length();c++)
{
     flg=true;
     char ch=str.charAt(c);
     int c1=c+1;
     
     while(c1<str.length())
     {
           if(ch==str.charAt(c1))
           {
             flg=false;
             break;
           }
      c1++;
     }

     if(flg==true)
     {
       System.out.println(ch);
       break;
      }
}

Myth: u r using string functions in here..which is not allowed..and if u will implement it..then it will take O(n) time..


and u r using... O[n^2] time complexity..

but we need O(n).. and space O(1)...

here is the program in C..compiled in DEV CPP compiler
###################
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>


#define ROW 26
#define COL 2


int main()
{

int i=0,j=0;
static int arr[ROW][COL];
int min=0,index=0;
char *s="xaseresabc";
char *ch=s;
while(*ch != '\0')
{
j=*ch - 97;
arr[j][0]++;
arr[j][1]=i;
i++;
ch++;

}

for(i=0;i<26;i++)
{
printf("%d %d\n",arr[i][0],arr[i][1]);
}

index=arr[0][1];
for(i=0;i<26;i++)
{
if((arr[i][0]==1) && (arr[i][1]<index))
{
index=arr[i][1];
min=i;
}
}

char ch1;
ch1= min + 97;
printf("the string is:%s\n",s);

printf("the first unrepeated character is:%c\n",ch1);

getch();
return 0;
}

a little bit modification...
###################
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define ROW 26
#define COL 2
char first_un(char *p);

int main()
{

int i=0,j=0;
static int arr[ROW][COL];
int min=0,index=0;
static int indexi;
char *s="xaserbyxeypsxrabc";
char *ch=s;
while(*ch != '\0')
{
j=*ch - 97;
arr[j][0]++;
arr[j][1]=i;
i++;
ch++;



}

for(i=0;i<26;i++)
{
printf("%d %d\n",arr[i][0],arr[i][1]);

if(arr[i][0]==1)
{
indexi=arr[i][1];
break;
}
}

//index=arr[0][1];
printf("the static index is:%d\n",indexi);
index=indexi;
for(i=0;i<26;i++)
{

if((arr[i][0]==1) && (arr[i][1]<index))
{
index=arr[i][1];
min=i;
}


}

char ch1;
ch1= min + 97;
printf("the string is:%s\n",s);
printf("the value of min is:%d\n",min);
printf("the first unrepeated character is:%c\n",ch1);

getch();
return 0;
}



#############

asetech: your program bounced for the following input: bbccdbccefee ->

souravgh@souravgh-AOD255:~/NetBeansProjects/MaxPath$ ./test
0 0
3 5
4 7
1 4
the static index is:4
the string is:bbccdbccefee
the value of min is:0
the first unrepeated character is:a

Here is the O (n) time and O (1) space solution:

// Find the first non repeating character in a string.
// (c) souravgh@usc.edu
// Sat Feb 12 1750
#include <cstdio>
#include <cstdlib>

using namespace std;

#define NoCharsInt 256

// Find and print the first non repeating character
// from the given string.
// O (n) time, O (1) space.
void printFirstNonRepeat (const char *strCharPtr) {
  int charCountIntPtr[NoCharsInt]; // O (1) space

  // Initialize constant size array
  // O (1)
  for (int indexInt = 0; indexInt < NoCharsInt; indexInt++) {
    charCountIntPtr[indexInt] = 0;
  }

  // Get the occurence of every character.
  // O (n)
  for (char *tempCharPtr = (char *)strCharPtr; 
       *tempCharPtr; 
       ++charCountIntPtr[*tempCharPtr], tempCharPtr++);

  // Find first non repeating character.
  // O (n)
  for (char *tempCharPtr = (char *)strCharPtr; *tempCharPtr; tempCharPtr++) {
    if (charCountIntPtr[*tempCharPtr] == 1) {
      printf ("First non repeating character = %c\n", *tempCharPtr);
      return;
    }
  }

    printf ("No non repeating character found in string.\n");
}

int main (void) {
  const char *strCharPtr = "bcdbcefe";

  printFirstNonRepeat (strCharPtr);

  return EXIT_SUCCESS;
}

This can be used to find the nth non repeating character in a string.

1. Represent each character by numbers using their Ascii values.
2. Put them in array.
3. XOR each value in variable.
4. Get corresponding Ascii value of non-repeated character in the variable.
5. Print out the non repeated character.

There is another simple way.
1. Reverse string. O(n)
2. Keep tracking of a unique character. If there is a unique character. Point it. Return the last unique character.

It solves the problem without extra memory and O(n) time.

@Towhid
How will you find out the unique character? Can you please elaborate your algorithm

One more method with O(nlogn + n) time complexity and no extra space, however
if we are allowed to modify original string then this would work.
Sort the characters based on their ascii values - Merge Sort O(nlogn)
Scan through the string to check next and previous values, ignoring non-repeating values.

Second method, but which adds little bit space complexity O(n) in worst case and Time Complexity O(n log n) is about constructing Binary Search Tree, here nodes represent two things key = character in the string and
value = occurrence count
Now create nodes in tree as we encounter new characters, with value = 1.
As we get subsequent occurrences of the same key, increment value.
At the end, print nodes (i.e. key, where values = 1), delete BST once things are done.
Scanning thorough list O(n), which involves computing of BST for each character thus
O(n logn), however if characters are repeated the BST operations would be quick also we an think of replacing BST with even Hash Table but then it would be same as previous methods described above...