# Determine whether one string is a permutation of the other

Question 1.3 of Cracking the Coding Interview:

Given two strings, write a method to decide if one is a permutation of the other.

Two strings are a “permutation” if they contain the same distribution of characters. So one solution is to build this distribution for each string, and check whether those distributions are the same. For example, `"hello"` and `"ehlol"` are permutations of each other, because they both have the same character distribution, `{e: 1, h: 1, l: 2, o: 1}`.

Here’s a solution in C. It represents the character distribution as an `int`, where `distrib[c]` gives the count of the character `c`.

``````#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

void char_distrib(char* s, int distrib[]) {
for (int i = 0; s[i] != '\0'; i++) {
distrib[s[i]]++;
}
}

bool is_permutation(char* a, char* b) {
int* a_distrib = calloc(255, sizeof(int));
int* b_distrib = calloc(255, sizeof(int));
char_distrib(a, a_distrib);
char_distrib(b, b_distrib);
for (int i = 0; i < 256; i++) {
if (a_distrib[i] != b_distrib[i]) return false;
}
return true;
}

void test(char* a, char* b, bool output) {
assert(is_permutation(a,b) == output);
}

int main(int argc, char** argv) {
test("hello", "ehlol", true);
test("hell", "ehlol", false);
test("", "", true);
return 0;
}
``````

This runs in `O(len(a)+len(b))` and uses constant memory. This is optimal, because we at least have to look at every character, which is already linear time.

The other “obvious” solution is to sort both strings and check they’re the same. But this is less efficient, and harder to implement in C.

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only \$19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s \$29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

### More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer.