Unique Characters – Occurrence Order

Remove duplicate characters from a string while preserving the order of their first occurrence

Understand the Problem

Problem Statement

Given a string S, the program must remove duplicate characters and print only the unique characters in the order they first appear in the string.

This is a fundamental string manipulation problem that tests understanding of character tracking and order preservation.

Constraints

1 ≤ Length of string S ≤ 1000
String S can contain any printable ASCII characters (letters, digits, spaces, special characters)
Case sensitivity matters (uppercase and lowercase letters are treated as different characters)
Space characters are valid and should be preserved if they appear

Examples

Example 1

Input

100 apples

Output

10 aples

Explanation

The character '1' appears first, then '0' (appears twice but only first occurrence is kept), then space, then 'a', 'p' (appears twice), 'l', 'e', 's'. The duplicate '0' and 'p' are removed while preserving order.

Example 2

Input

hello world

Output

helo wrd

Explanation

Characters 'l' and space appear multiple times, but only their first occurrence is kept. The result maintains the original order of first appearances.

Example 3

Input

programming

Output

progamin

Explanation

The characters 'r', 'o', 'g' appear multiple times. Only the first occurrence of each is kept, resulting in 'progamin' while preserving the original order.

Solution

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

#define MAX_LEN 1001
#define ASCII_SIZE 128

int main() {
    char s[MAX_LEN];
    char result[MAX_LEN];
    int seen[ASCII_SIZE] = {0}; // Track seen characters using ASCII values
    int resultIndex = 0;
    
    // Read entire line including spaces
    fgets(s, MAX_LEN, stdin);
    
    // Remove newline character if present
    int len = strlen(s);
    if (s[len-1] == '\n') {
        s[len-1] = '\0';
    }
    
    // Process each character
    for (int i = 0; s[i] != '\0'; i++) {
        char current = s[i];
        
        // If character hasn't been seen before
        if (!seen[(int)current]) {
            seen[(int)current] = 1;  // Mark as seen
            result[resultIndex++] = current;  // Add to result
        }
    }
    
    result[resultIndex] = '\0';  // Null terminate result string
    printf("%s\n", result);
    
    return 0;
}

Time:O(n) where n is the length of the input string. We process each character exactly once.

Space:O(1) for the seen array (fixed size 128) + O(n) for result storage in worst case (all unique characters).

Approach:

C Solution Explanation:

Character Tracking: Uses an integer array seen[128] where each index represents an ASCII character value (0-127)
Input Reading: Uses fgets() to read the entire line including spaces
Processing Loop: Iterates through each character in the input string
Duplicate Detection: Checks if seen[current_char] is 0 (not seen) or 1 (already seen)
Result Building: Only adds characters to result if they haven't been seen before
Output: Prints the final result string with duplicates removed

The ASCII array approach is efficient for this constraint since all printable characters fall within ASCII range 0-127.

Visual Explanation

Loading diagram...

All Problems