Check if a String Has All Unique Characters in C

To check whether a string contains all unique characters in C, you can compare each character with every other character, using an auxiliary data structure, or applying bit manipulation for optimized performance.

Example 1: Using Nested Loops

In this example, we use nested loops to compare every character with each subsequent character in the string.

main.c

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

int hasAllUniqueChars(char str[]) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (str[i] == str[j])
                return 0; // Duplicate found
        }
    }
    return 1; // All characters are unique
}

int main() {
    char str[] = "abcdefg";
    if (hasAllUniqueChars(str))
        printf("All characters are unique.");
    else
        printf("Duplicate characters found.");
    return 0;
}

Explanation:

  1. hasAllUniqueChars: A function that takes a string and returns 1 if all characters are unique, otherwise 0.
  2. strlen(str): Calculates the length of the string. Refer: string strlen()
  3. The outer for loop iterates through each character of the string.
  4. The inner for loop compares the current character with all following characters.
  5. If a duplicate is found, the function returns 0 immediately.
  6. If no duplicates are found, the function returns 1 after checking all characters.

Output:

All characters are unique.

Example 2: Using a Frequency Array

In this example, we use an auxiliary array to count the frequency of each character. This method assumes the character set is ASCII (256 characters).

main.c

</>
Copy
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int hasAllUniqueChars(char str[]) {
    int freq[256] = {0};
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (freq[(int)str[i]] == 1)
            return 0; // Duplicate found
        freq[(int)str[i]] = 1;
    }
    return 1; // All characters are unique
}

int main() {
    char str[] = "hello";
    if (hasAllUniqueChars(str))
        printf("All characters are unique.");
    else
        printf("Duplicate characters found.");
    return 0;
}

Explanation:

  1. freq: An integer array of size 256 initialized to 0, used to store the occurrence of each ASCII character.
  2. strlen(str): Calculates the length of the string. Refer: string strlen()
  3. The for loop iterates over each character in the string.
  4. For each character, its ASCII value is used as an index in the freq array.
  5. If the frequency at that index is already 1, it means the character has appeared before, so the function returns 0.
  6. If no duplicate is found, the frequency is set to 1 and the loop continues until all characters are checked.

Output:

Duplicate characters found.

Example 3: Using Bit Manipulation (for Lowercase Letters Only)

In this example, we apply bit manipulation to check for unique characters in a string. This method is efficient but only works for lowercase alphabets (‘a’ to ‘z’).

main.c

</>
Copy
#include <stdio.h>

int hasAllUniqueChars(char str[]) {
    int checker = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        int val = str[i] - 'a';
        if (checker & (1 << val))
            return 0; // Duplicate found
        checker |= (1 << val);
    }
    return 1; // All characters are unique
}

int main() {
    char str[] = "world";
    if (hasAllUniqueChars(str))
        printf("All characters are unique.");
    else
        printf("Duplicate characters found.");
    return 0;
}

Explanation:

  1. checker: An integer used as a bit vector to store the occurrence of each character.
  2. The for loop iterates over the string until the null terminator (\0) is reached.
  3. For each character, val calculates its offset from ‘a’.
  4. checker & (1 << val) checks if the bit corresponding to the character is already set.
  5. If the bit is set, the function returns 0, indicating a duplicate character.
  6. If not, checker |= (1 << val) sets the bit for that character and continues the loop.

Output:

All characters are unique.

Conclusion

In this tutorial, we covered three different methods to check if a string has all unique characters in C:

  1. Nested Loops: A straightforward approach by comparing each character with every other character.
  2. Frequency Array: Uses an auxiliary array to track occurrences of each character (suitable for ASCII).
  3. Bit Manipulation: An efficient method for strings that only contain lowercase alphabets.