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[255], 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.

I just released Vidrio, a free app for macOS and Windows to make your screen-sharing awesomely holographic. Vidrio shows your webcam video on your screen, just like a mirror. Then you just share or record your screen with Zoom, QuickTime, or any other app. Vidrio makes your presentations effortlessly engaging, showing your gestures, gazes, and expressions. #1 on Product Hunt. Available for macOS and Windows.

With Vidrio

With generic competitor

More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.