main.c

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

// void sort(char *s) {
//     size_t n = strlen(s);
//     for (size_t i = 0 ; i < n - 1; ++i) {
//         for (size_t j = i + 1 ; j < n; ++j) {
//             if (s[i] > s[j]) {
//                 char temp = s[i];
//                 s[i] = s[j];
//                 s[j] = temp;
//             }
//         }
//     }
// }

// int is_permutation(char *s1, char *s2) {
//     if (strlen(s1) != strlen(s2)) {
//         // Costs: o(n)
//         return 0;
//     }
//     // Costs: o(nlogn)
//     sort(s1);
//     // Costs: o(nlogn)
//     sort(s2);
//     return strcmp(s1, s2) == 0;
//     // o(n) + o(nlogn) + o(nlogn) = o(nlogn)
// }

int is_permutation(const char *s1, const char *s2) {
    if (strlen(s1) != strlen(s2)) {
        // O(n)
        return 0;
    }

    char letters[256] = { 0 };
    for (size_t i = 0; i < strlen(s1); ++i) {
        // O(n)
        letters[s1[i]]++;
    }
    for (size_t i = 0; i < strlen(s2); ++i) {
        // O(n)
        letters[s2[i]]--;
        if (letters[s2[i]] < 0) {
            return 0;
        }
    }
    return 1;
    // O(n)
}

int main(int argc, char **argv) {
    if (argc != 3) {
        printf("Usage: %s <str1> <str2>\n", argv[0]);
        return 1;
    }
    if (is_permutation(argv[1], argv[2])) {
        printf("This is a permutation :)\n");
    } else {
        printf(":(\n");
    }
    return 0;
}