Remove the Duplicate Characters

Description

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not. FOLLOW UP Write the test cases for this method.

Tips:

  • Confirm how to order the string after removed the duplicates. Exp. "accffcfa" could be either "acf" or "cfa" after removing duplicates
  • Confirm if an array with fixed size is allow to use, or no array is allowed at all.
  • If a fixed sized array is allowed, we can use it to count the occurrence of the characters.
  • Use [NSString stringByReplacingOccurrencesOfString] to replace the duplicated characters with “”, it has the same effect with delete function.

Pseudo-code

1
2
3
4

for(from 0 to (n-1) of the string)
{
  apply replacing the current character with "" to the rest of the string;
}

My Objective-C Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 Time complexity: O(n)
 Space: O(1)
 */
- (NSString *) removeDuplicate1_3:(NSString *)s
{
    if (nil == s || [s length] < 2) return s;
    for (NSUInteger n = 0; n < [s length] - 1; n ++)
    {
        s = [s stringByReplacingOccurrencesOfString:[s substringWithRange:NSMakeRange(n, 1)]
                                         withString:@""
                                            options:0
                                              range:NSMakeRange(n + 1, [s length] - n - 1)];
    }
    return s;
}

My Objective-C Solution 2

This solution requires an additional fixed size array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 Time complexity: O(n)
 Space: O(256)
 */
- (NSString *) removeDuplicate1_3_2:(NSString *)s
{
    if (nil == s || [s length] < 2) return s;

    NSMutableArray *array = [NSMutableArray array];

    NSUInteger i = 0;

    while (i < 256)
    {
        [array addObject:[NSNumber numberWithBool:NO]];
        i++;
    }

    for (NSUInteger n = 0; n < [s length]; n ++)
    {
        BOOL hasAppeared = [[array objectAtIndex: (NSUInteger)[s characterAtIndex:n]] boolValue];
        if (hasAppeared)
        {
            s = [s stringByReplacingCharactersInRange:NSMakeRange(n, 1)
                                           withString:@""];
            n--;
        }
        else
        {
            [array replaceObjectAtIndex:(NSUInteger)[s characterAtIndex:n]
                             withObject:[NSNumber numberWithBool:YES]];
        }
    }
    return s;
}

Test the Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

- (void)viewDidLoad
{
    [super viewDidLoad];

    NSString *s1 = @"abcde";
    NSString *s2 = @"aaabbb";
    NSString *s3 = @"";
    NSString *s4 = @"abababc";
    NSString *s5 = @"ccccc";

    NSLog(@"%@", [self removeDuplicate1_3:s1]);
    NSLog(@"%@", [self removeDuplicate1_3:s2]);
    NSLog(@"%@", [self removeDuplicate1_3:s3]);
    NSLog(@"%@", [self removeDuplicate1_3:s4]);
    NSLog(@"%@", [self removeDuplicate1_3:s5]);

}

Comments