#include <stdio.h>
/*
* Finds the first repeated character in a string.
*
* Examples:
* "abca" -> 'a'
* "abcbd" -> 'b'
* "abcde" -> '\0' (no repeated character)
* "abcdxypcbop" -> 'c'
*
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
char findFirstRepeatedCharacter(const char *str)
{
if (str == NULL) {
return '\0';
}
// Tracks whether a character has been seen before.
int seen[256] = {0};
while (*str) {
unsigned char ch = (unsigned char)*str;
// If we've already seen this character,
// it's the first repeated character.
if (seen[ch]) {
return ch;
}
seen[ch] = 1;
str++;
}
// No repeated character found.
return '\0';
}
int main(void)
{
char result;
result = findFirstRepeatedCharacter("abca");
printf("%c\n", result ? result : ' '); // a
result = findFirstRepeatedCharacter("abcbd");
printf("%c\n", result ? result : ' '); // b
result = findFirstRepeatedCharacter("abcde");
printf("%c\n", result ? result : ' '); //
result = findFirstRepeatedCharacter("abcdxypcbop");
printf("%c\n", result ? result : ' '); // c
return 0;
}
/*
run:
a
b
c
*/
