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[26]; 
        Arrays.fill(count, Integer.MAX_VALUE);
        for (String str : A) {
            int[] cnt = new int[26];
            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

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Common Characters”

  1. Globules said
    May 15, 2019 at 2:59 AM

    A Haskell version.

    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
    May 17, 2019 at 5:49 AM

    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
    June 30, 2019 at 1:48 AM

    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[26] = {0};
  int a2[26] = {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[1], argv[i]);
  }
  printf("%s\n", argv[1]);
  return EXIT_SUCCESS;
}

    Example Usage:

    $ ./a.out bella label roller
ell

Leave a comment