CareerCup

0. Keep boolean array for each character
1. Read string from left to right, Keep setting ith character value in boolean array
2. If you see a character whose bit is already set, return the character

Sort it and then scan it (compare arr[I]==arr[I+1])

Assuming a character set domain of 65535 characters, we can have a hashmap of size 65535.
Whenever we find a character not present in hashmap, we just insert it.
When we find a character present, we return with that character.

This is space intensive approach.

@Anonymous: Sorting a large string would be extremely cumbersome w.r.t time required.

use namespace std;
class map {

private:
map<char,boolean> map;

public:
char processString(char * p){
int i=0;
while(i++ < strlen℗) {
if( map.find(p[i])==null){
map.add(p[i], true);
}
else {
return p [i];
}
}
int main() {
String readline;
cout<<"Enter the String"<<endl;
cin>>readline;
cout>>"First repeating charcter in the string">>processString(readline);
}
}

the same can also be done by storing the scanned characters of the String in a char array and using an efficient binary search to check the presence of a character in the array during the next insertion.

#include<iostream>

using namespace std;

void findFirstRepeatedChar(char m[], int length)
{
bool isExisted[256];
for(int i = 0; i < 256; i++)
isExisted[i] = false;

for(int i = 0; i < length; i++)
{

if(true == isExisted[m[i]])
{
cout<<m[i]<<endl;
return;
}
else
{
isExisted[m[i]] = true;
}
}
}
void main()
{
char a[] = "abcdefgbaew";
findFirstRepeatedChar(a, sizeof(a)/sizeof(char));
}

u can add each char in a bst and if u find the repeating char u can simply print it.For inserting in bst it takes only Olog n)..

Create a boolean array, arr[26] and initialize it to 0
arr[0] corresponds to 'a'
arr[1] corresponds to 'b'
.
.
.
arr[25] corresponds to 'z'

Now suppose the string is "madame"
Scan the string, and for every character turn the boolean value in array to 1.
If there is a duplicate value, it would have already been encountered before for that index and the flag would already be 1, and hence the duplicate could be found.

for ex:
here
'm' => arr[ascii('m')- 65] = 1; // arr[12]=1
'a' => arr[ascii('a')- 65] = 1; // arr[0]= 1
'd' => arr[ascii('d')- 65] = 1; // arr[3] = 1
'a' => arr[ascii('a')- 65] is already 1, so this is the duplicate element.

Please let me know if there's something wrong with this approach.

Create a boolean array, arr[26] and initialize it to 0
arr[0] corresponds to 'a'
arr[1] corresponds to 'b'
.
.
.
arr[25] corresponds to 'z'

Now suppose the string is "madame"
Scan the string, and for every character turn the boolean value in array to 1.
If there is a duplicate value, it would have already been encountered before for that index and the flag would already be 1, and hence the duplicate could be found.

for ex:
here
'm' => arr[ascii('m')- 65] = 1; // arr[12]=1
'a' => arr[ascii('a')- 65] = 1; // arr[0]= 1
'd' => arr[ascii('d')- 65] = 1; // arr[3] = 1
'a' => arr[ascii('a')- 65] is already 1, so this is the duplicate element.

Please let me know if there's something wrong with this approach