## Common Characters

### May 14, 2019

We work with two words at a time, repeating as needed for longer lists. Our method sorts the letters of the two words in order, then scans the two lists, keeping characters that match:

```(define (common x-str y-str)
(let loop ((xs (sort charlist x-str)))
(ys (sort charlist y-str)))
(zs (list)))
(cond ((or (null? xs) (null? ys))
(list->string (reverse zs)))
((char<? (car xs) (car ys))
(loop (cdr xs) ys zs))
((char<? (car ys) (car xs))
(loop xs (cdr ys) zs))
(else (loop (cdr xs) (cdr ys)
(cons (car xs) zs))))))```
```(define (common-chars . words)
(fold-left common (car words) (cdr words)))```

And here’s the sample problem:

```> (common-chars "bella" "label" "roller")
"ell"```

You can run the program at https://ideone.com/MVtnY0.

The sample solution at the coding challenge site looks like this:

```public List commonChars(String[] A) {
List ans = new ArrayList();
int[] count = new int;
Arrays.fill(count, Integer.MAX_VALUE);
for (String str : A) {
int[] cnt = new int;
for (char c : str.toCharArray()) { ++cnt[c - 'a']; } // count each char's frequency in string str.
for (int i = 0; i < 26; ++i) { count[i] = Math.min(cnt[i], count[i]); } // update minimum frequency.
}
for (char c = 'a'; c  0) { ans.add("" + c); }
}
return ans;
}```

That solution has four `for` loops and one `while` loop (some of them nested), an `ArrayList` data structure for the return value, an `int[]` array for each word plus another `int[]` array for the totals (and their names `cnt` and `count` are sure to be confused), lots of funny character arithmetic, and the magic numbers 26 and `'a'` and `'z'` and `Integer.MAX_VALUE`. With all that complexity it takes a few minutes of slow reading for the underlying algorithm to become apparent. I like my solution better.

Pages: 1 2

### 3 Responses to “Common Characters”

1. Globules said

```import Data.List (foldr1, intersect)

common :: Eq a => [[a]] -> [a]
common []  = []
common xss = foldr1 intersect xss

main :: IO ()
main = do
print \$ common ([] :: [String])
print \$ common ["BELLA"]
print \$ common ["BELLA", "LABEL"]
print \$ common ["BELLA", "LABEL", "ROLLER"]
```
```\$ ./commchar
""
"BELLA"
"BELLA"
"ELL"
```
2. Paul said

In Python.

```from collections import Counter
from functools import reduce
from operator import and_

def common(listofwords):
return list(reduce(and_, (Counter(w) for w in listofwords)).elements())

print(common(["BELLA", "LABEL"]))  # -> ['B', 'E', 'L', 'L', 'A']
print(common(["BELLA", "LABEL", "ROLLER"]))  # -> ['E', 'L', 'L']
```
3. Daniel said

Here’s a solution in C.

```#include <stdio.h>
#include <stdlib.h>

// Returns the result in s1
void common(char* s1, char* s2) {
int a1 = {0};
int a2 = {0};
char* _s1 = s1;
for (; *s1; ++s1) {
++(a1[*s1 - 'a']);
}
for (; *s2; ++s2) {
++(a2[*s2 - 'a']);
}
int pos = 0;
for (int i = 0; i < 26; ++i) {
int count = a1[i] < a2[i] ? a1[i] : a2[i];
for (int j = 0; j < count; ++j) {
_s1[pos++] = 'a' + i;
}
}
_s1[pos] = '\0';
}

int main(int argc, char* argv[]) {
if (argc == 1) return EXIT_FAILURE;
for (int i = 1; i < argc; ++i) {
common(argv, argv[i]);
}
printf("%s\n", argv);
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./a.out bella label roller
ell
```