[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – 중복 글자 없애기

Given a string, you have remove duplicates from it in O(n) time and O(1) space.

 

for example:

abcbaad ==> abcd

 

limitations

1. just use O(n) times

2. just use O(1) space

 

solution: Just using lookup table, make 256 bytes char map, and insert char which is founded. and check it. if ch is not 0, it already exists. at that time just skip that character.

if you want to reduce memory size, using Bit Vector and then you will use just 32 bytes.

 


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main( int argc, char *argv[] )
{
 unsigned char bitmap[256];
 memset( bitmap, 0, 256 );

unsigned char *ch = (unsigned char *)argv[1];
 while( *ch != '\0' ) {
 if( bitmap[*ch] == '\0' ){
 bitmap[*ch] = 1;
 printf("%c", *ch );
 }
 ch++;
 }
 printf("\n");

return 0;
}