19
\$\begingroup\$

Find characters common among all strings

You are given multiple Strings as an input. Your task is to find the characters that are present in every string, and return them in any order. There may be duplicates.

If the same character is present in all strings more than once, you have to return multiple copies of it.

Example:

  • Input: "cattle", "throttle", "rotten", "torrent"

  • Output: 't', 'e', 't'

  • Input: "cattle", "throttle", "rotten", "tree"

  • Output: 't', 'e'

  • Input: "hauberk", "ill"

  • Output:

  • Input: "haunt", "haunting-haunt"

  • Output: 'h', 'u', 'a', 't', 'n'

Constraints

  • Input is only ASCII
  • 1 <= input length <= 100
  • 1 <= input[i] length <= 100

I/O format

Flexible w/ default I/O policies.

$$Let's\ see\ your\ shortest\ solutions!$$

\$\endgroup\$
9
  • 3
    \$\begingroup\$ Suggested test case: "cattle", "throttle", "rotten", "tree" (which should give 't', 'e' if I understand correctly). \$\endgroup\$
    – Arnauld
    Commented Jun 8 at 21:13
  • \$\begingroup\$ I have a feeling this should be closed as a dupe for "set intersection", but theres multiple challenges and all are subtly different so idk \$\endgroup\$
    – Seggan
    Commented Jun 8 at 22:23
  • 2
    \$\begingroup\$ @Seggan Set intersection would not have duplicates in the output. \$\endgroup\$
    – chunes
    Commented Jun 8 at 22:56
  • \$\begingroup\$ ascii only invalidates plenty of languages with custom codepages... \$\endgroup\$
    – pacman256
    Commented Jun 9 at 0:11
  • 2
    \$\begingroup\$ @pacman256 I thought he meant that the input was ascii only? \$\endgroup\$
    – Neil
    Commented Jun 9 at 0:29

21 Answers 21

7
\$\begingroup\$

Jelly, 3 bytes

œ&/

Takes a single input argument with a list of strings.

Try it online!

Explanation

Reduce (/) using multiset intersection (œ&).

\$\endgroup\$
7
\$\begingroup\$

Python, 65 60 bytes

-5 thanks to Jitse (unnecessary generator-to-list inside join(): -2; replace set(X) with {*X}: -3)

lambda L:"".join(a*min(w.count(a)for w in L)for a in{*L[0]})

Attempt This Online!

lambda L:"".join(               # Return a string by concatenating a sequence of
    a*                          # - letters
      min(w.count(a)for w in L) #   - multiplied by the minimum common count,
    for a in                    #   - taken from
     {*L[0]}                    #       unique letters from the first string.
)

A previous, 7 bytes more expensive, solution had ...join(L and[...]) to account for the case of empty input, that was later clarified to be out of scope.


Discarded approaches: reduce (112 108 bytes) and recursive (100 bytes)

The most popular genre of the other answers, i.e. "reduce/fold multiset intersection", doesn't have a direct port to Python (no multisets). The closest would be using Counters but the imports are very verbose, and so is the .elements() method to make the results a primitive.

Explicit (112 bytes, Attempt This Online!):

lambda L:[*reduce(lambda a,b:(k:=Counter)(a)&k(b),L).elements()]
from functools import*
from collections import*

Further golfed by Stef (108 bytes, Attempt This Online!):

lambda L:[*reduce((k:=Counter).__and__,map(k,L)).elements()]
from functools import*
from collections import*

We save only a few bytes by replacing reduce with recursion (100 bytes, Attempt This Online!)

from collections import*
k=Counter
f=lambda L:[*(k(L[0])&k(f(L[1:]))).elements()]if L[1:]else[*L[0]]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -4bytes on the reduce version: lambda L:[*reduce((k:=Counter).__and__,map(k,L)).elements()] \$\endgroup\$
    – Stef
    Commented Jun 10 at 19:01
4
\$\begingroup\$

R, 49 bytes

\(S)Reduce(\(x,y)y[pmatch(x,y,0)],strsplit(S,""))

Attempt This Online!

Or alternatively, this 66 bytes version:

R, 66 bytes

\(S,`+`=make.unique)Reduce(\(x,y)y[match(+x,+y,0)],strsplit(S,""))

Attempt This Online!

In the both cases the function pmatch/match compares two words (vectors of the characters) and outputs the positions of the matching characters, while subsetting produces the characters themselves. Reduce runs this process quasi-recursively and finally outputs only those characters which matched all words.

\$\endgroup\$
4
\$\begingroup\$

K(ngn/k), 8 20 10 bytes

-10 bytes thanks to ovs.

&&/#''=:'

Try it here!

20 bytes verison

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Just {&&/#''='x} or &&/#''=:' as a tacit function works \$\endgroup\$
    – ovs
    Commented Jun 9 at 13:15
3
\$\begingroup\$

J, 21 bytes

a.#~[:<./+/@(=/&a.)&>

Try it online!

Takes input as list of boxed words.

  • For each word in the list:
    • For each letter in the word:
      • Create a length 256 bit mask corresponding to the ascii alphabet, which is 1 if the letter equals that ascii character and 0 otherwise.
    • Sum those bit masks. Now we have length 256 array, with each position giving us the letter count within the word.
  • Take the element-wise min across all those length 256 letter counts.
  • Use that new count mask to duplicate the letters of the ascii alphabet.
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 40 bytes

%O`.
!`(.)(?<=^.*(\1+))(?=.*(¶.*\2.*)*$)

Try it online! Takes each string on its own line and outputs each common character in ASCII order on its own line. Explanation:

%O`.

Sort each string into ASCII order.

!`(.)

Output all characters...

(?<=^.*(\1+))

... from the first string, counting how many times this character has appeared so far...

(?=.*(¶.*\2.*)*$)

... that appear that many times in all of the other strings as well.

\$\endgroup\$
2
\$\begingroup\$

NARS2000 (APL), 3 characters; 6 bytes

∩⍦/

/ reduce using

 multi-set

   intersection

enter image description here

\$\endgroup\$
2
\$\begingroup\$

Haskell + hgl, 5 bytes

lH nx

Fold by multiset intersection.

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

Vyxal 3 l, 3 bytes

/Þ⁾

Try it Online! (link is to literate version)

uses literate mode, ends up being a port of jelly anyways due to weird behavior in the set intersection

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 1. you have an h flag. 2. This is not right, try adding a t to cattle and it will result in ttet. \$\endgroup\$ Commented Jun 9 at 14:16
2
\$\begingroup\$

R, 81 bytes

\(l)rep(y<-unique(el(x<-strsplit(l,""))),Map(\(a)min(sapply(x,\(s)sum(s==a))),y))

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 18 bytes

WS⊞υιΦθ⬤υ›№λι№…θκι

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

WS⊞υι

Read the input into an array.

 θ              First string
Φ               Filtered where
   υ            List of strings
  ⬤             All satisfy
     №          Count of
       ι        Current character
      λ         In current string
    ›           Is greater than
        №       Count of
            ι   Current character
          θ     In first string
         …      Truncated to length
           κ    Outer index

Taking the input as a JSON array would save 3 bytes, as υ would be replaced with θ which itself would have to be replaced with ⌊θ (which isn't necessarily the first string but it will be consistent which is all that's required here).

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES10), 62 bytes

Expects words as arrays of characters and returns in the same format.

a=>a.reduce((s,w)=>s.flatMap(c=>w.splice(w.indexOf(c)>>>0,1)))

Try it online!

Commented

a =>                // a[] = input array
a.reduce((s, w) =>  // for each word w[] in a[], with accumulator s[]:
  s.flatMap(c =>    //   for each character c in s[]:
    w.splice(       //     remove from w[]:
      w.indexOf(c)  //       the first occurrence of c in w[]
      >>> 0,        //       if not found, we turn the index -1 into
      1             //       the maximum unsigned 32-bit value so that
                    //       nothing is removed
    )               //     end of splice() -> returns [c] or []
  )                 //   end of flatMap() -> removes all empty entries
)                   // end of reduce()
\$\endgroup\$
2
\$\begingroup\$

Haskell, 75 bytes

import Data.List
f x=[y|y<-mapM(group.sort)x,[z]<-[nub$concat y]]>>=minimum

Try it online!

Explanation:

  • group . sort sorts the characters of a given string, and then splits the result into a list of substrings, each composed of multiple occurrences of the same character (e.g. (group . sort) "cattle" is equal to ["a", "c", "e", "l", "tt"]); the sort is necessary to ensure that all occurrences of a given character are contiguous before the group.
  • mapM g x is the cartesian product of the lists in map g x *; for example, let ys = mapM g ["cattle", "throttle", "rotten", "torrent"] where g = (group . sort):
    • the first element of ys is ["a", "e", "e", "e"], where "a" is the first element of g "cattle", the first "e" is the first element of g "throttle", and so on;
    • the last element of ys is ["tt", "ttt", "tt", "tt"], where the first "tt" is the last element of g "cattle", "ttt" is the last element of g "throttle", and so on.
  • Then, nub $ concat y concatenates all substrings of y, and nub keeps only the first occurrence of each character; for example:
    • nub $ concat ["a", "e", "e", "e"] is "ae",
    • nub $ concat ["tt", "ttt", "tt", "tt"] is "t".
  • With the [z] <- ... syntax we select only the ys such that nub $ concat y comprises a single element, since the pattern match fails if nub $ concat y has zero or more than one element; for example, the first element of ys is filtered out, while the last element of ys is kept; as a consequence, we select only those ys that contain only substrings that all contain the same character.
  • Finally, (>>= minimum) is equivalent to concatMap minimum; minimum applied to a list like ["tt", "ttt", "tt", "tt"] selects the shortest string, so it select the substring containing n occurrences of the same character so that every string of the initial input contains at least n occurrences of the considered character; the concat is applied so the function returns "ett" and not ["e", "tt"].

*: the cartesian product is a very inefficient and unnecessary step for solving the problem, but it allows for a short(er) solution

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you add an explanation? There's some cool stuff I don't understand going on in this answer, and I want to be able to fully appreciate it. \$\endgroup\$
    – DLosc
    Commented Jun 11 at 22:04
  • 1
    \$\begingroup\$ @DLosc done, hope it's clear enough. Thank you for your interest :) \$\endgroup\$
    – matteo_c
    Commented Jun 15 at 12:36
1
\$\begingroup\$

vemf, 5 bytes

Takes a list of strings.

ϖ֨\

Though vemf has no built-in multiset intersection, it doesn't do too badly, because û is made to implement multiset operations anyways (stolen from BQN, which doesn't happen to have an entry). The obvious solution would be Reduce │û\╓¿ Multiset Intersection, but it turns out leaving the Nones there until the end saves 1 byte. online

\$\endgroup\$
1
\$\begingroup\$

Zsh & coreutils, 110 93 bytes

d()(<<<$1|fold -1|sort)
m=$1;while ((#>1))do m=`comm -12 <(d $m) <(d $2)`;shift;done
<<<$m|rs

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ TODO: try using the ${name:*arrayname} array intersection. \$\endgroup\$
    – roblogic
    Commented Jun 10 at 12:19
1
\$\begingroup\$

Uiua SBCS, 17 16 bytes

⍜-(⊚/↧⬚0∵◇°⊚)@\0

Try it!

-1 thanks to Tbw

\$\endgroup\$
1
  • \$\begingroup\$ You can drop the left paren by bringing the constant null outside of the under. \$\endgroup\$
    – Tbw
    Commented Jun 11 at 4:52
1
\$\begingroup\$

Perl 5 -MList::Util=min,pairmap -plF, 77 bytes

map$r[$.-1]{$_}++||$l{$_}++,@F}{pairmap{$\.=$b==$.&&$a x min map$$_{$a},@r}%l

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Uiua, 19 characters

▽≡/↧:⟜(∵◇/+⊞=)◴/◇⊂.

Try it here!

\$\endgroup\$
0
\$\begingroup\$

Google Sheets, 279 bytes

=let(f,lambda(t,split(regexreplace(t,"\B|\b","→"),"→")),g,lambda(t,join(,sort(tocol(f(t))))),v,map(tocol(A:A,1),g),w,lambda(m,rows(v)=counta(ifna(filter(v,regexmatch(v,m))))),f(join(,unique(reduce(,f(A1),lambda(a,c,let(s,regexextract(g(A1),c&"+"),{a;ifs(w(s),s,w(c),c,1,)})))))))

Put the strings in cells A1:A and the formula in cell B1.

screenshot

Ungolfed:

=let( 
  f, lambda(t, split(regexreplace(t, "\B|\b", "→"), "→")), 
  g, lambda(t, join(, sort(tocol(f(t))))), 
  v, map(tocol(A:A, 1), g), 
  w, lambda(m, counta(v) = counta(ifna(filter(v, regexmatch(v, m))))), 
  r, reduce(, f(A1), lambda(a, c, let( 
    s, regexextract(g(A1), c & "+"), 
    vstack( 
      a, 
      ifs(w(s), s, w(c), c, 1, ) 
    ) 
  ))), 
  f(join(, unique(r)))  
)

The formula sorts characters within strings and finds repeated characters in A1 in the other strings, falling back to finding non-repeated characters in A1. When the number of matches is the same as the total number of strings, the repeated characters are included in the result (or ditto for a non-repeated character.) Finally, get uniques, possibly including repeated characters.

(Note: While this will give the correct result for all test cases presented in the question, it won't handle a triple like "aardvark" in A1 correctly when there are doubles like "lama" in other strings. Triples and above are fine in the rest of strings so "lama", "aardvark" does get the correct result. Note also that regex special characters are not escaped.)

\$\endgroup\$
2
  • 3
    \$\begingroup\$ I read "handle duplicates" here as "handle arbitrary amount of repetition". That's the usual intended meaning. \$\endgroup\$
    – Jonah
    Commented Jun 9 at 2:31
  • \$\begingroup\$ @Jonah yes... I agree that the usual intended meaning in computing obviously includes triples and above. The dictionary definition of "duplicate" mentions "twin, double, clone, match, mate, fellow, counterpart". Spreadsheet formula languages have no variables but constants only, and functions cannot have side-effects. Could not think of a concise way of handling the case where there are different triples or above in all strings. I will look at adding a slight improvement if and when there is a test case where the answer fails. \$\endgroup\$ Commented Jun 9 at 7:40
0
\$\begingroup\$

05AB1E, 9 bytes

ε{æ}.»Ãéθ

(Output is sorted.)

Try it online or verify all test cases.

Explanation:

ε          # Map over each string of the (implicit) input-list:
 {         #  Sort the characters in the string
  æ        #  Pop and push the powerset
   }.»     # After the map: reduce the list of lists of strings by:
      Ã    #  Keep powerset-strings which are present in both lists
       é   # Then sort the remaining powerset-strings by length
        θ  # And pop and push the last/longest one
           # (which is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Arturo, 68 bytes

$->L->join map unique L\0'a->repeat a min map L=>[enumerate&=>[&=a]]

Try it!

A port of Nicola Sap's Python answer. Takes input as a list of lists of characters as singleton strings.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.