import itertools as i
D=dict.fromkeys
I=isinstance
L=len
P=i.product
T=tuple
def w(s,q=[]):
 if s:
  if q:
   if Z:=q[-1][0]:yield from w(s[1:],q[:-1]+[(Z,q[-1][1]+[s[0]])])
   yield from w(s[1:],q+[(1>Z,[s[0]])])
  else:yield from w(s[1:],q+[(0,[s[0]])]);yield from w(s[1:],q+[(1,[s[0]])])
 else:yield T((a,T(set(b)))for a, b in q)
def p(s,l=0):
 if L(s)==1:yield T(s);return
 n=min(s,key=L)
 if m:=[n[x:y+1]for x in range(L(n))for y in range(x,L(n))if all(n[x:y+1]in a for a in s)]:
  for q in m:
   a,b=[[*filter(None,x)]for x in zip(*[j.split(q,1)for j in s])];x,y=[p(a,1)]if a else[],[p(b,1)]if b else[];yield from P(*(x+[(q,)]+y))
   if 1>l:yield(*[(u,)for u in D(a)],q,*[(u,)for u in D(b)])
  if 1>l:
   for j in w(s):
    if~-all(x[0]for x in j):yield from P(*[p(b,1)if a else[b]for a,b in j])
 else:s=[x for y in s for x in([[y],y][any(any(j in v for v in s if v!=y)for j in y)])];yield T([(u,)for u in sorted(set(s),key=s.index)])
def e(s):yield from map(''.join,P(*[[k]if I(k,str)else[*e(k),'']for k in s]))
def t(s):
 for i in s:
  if I(i,str):yield i
  elif any(I(j,str)for j in i):yield T(t(i))
  else:yield from t(i)
def f(s):s=s.split(', ');return min([((v:=T(t(i))),sum(~-(j in s)for j in e(v)))for i in set(p(s))],key=lambda x:x[1])
 
#main test cases
print(f('their'))
print(f('their, her'))
print(f('her, him'))
print(f('she, he'))
print(f('they, she, he'))
print(f('them, her, him'))
print(f('goca, oc, oca'))
print(f('goca, soca, oc, goce, soce'))
print(f('goca, soca, gsocae, goce, soce'))
print(f('goca, soca, gsxocae, goce, soce, xoce'))

aW1wb3J0IGl0ZXJ0b29scyBhcyBpCkQ9ZGljdC5mcm9ta2V5cwpJPWlzaW5zdGFuY2UKTD1sZW4KUD1pLnByb2R1Y3QKVD10dXBsZQpkZWYgdyhzLHE9W10pOgogaWYgczoKICBpZiBxOgogICBpZiBaOj1xWy0xXVswXTp5aWVsZCBmcm9tIHcoc1sxOl0scVs6LTFdK1soWixxWy0xXVsxXStbc1swXV0pXSkKICAgeWllbGQgZnJvbSB3KHNbMTpdLHErWygxPlosW3NbMF1dKV0pCiAgZWxzZTp5aWVsZCBmcm9tIHcoc1sxOl0scStbKDAsW3NbMF1dKV0pO3lpZWxkIGZyb20gdyhzWzE6XSxxK1soMSxbc1swXV0pXSkKIGVsc2U6eWllbGQgVCgoYSxUKHNldChiKSkpZm9yIGEsIGIgaW4gcSkKZGVmIHAocyxsPTApOgogaWYgTChzKT09MTp5aWVsZCBUKHMpO3JldHVybgogbj1taW4ocyxrZXk9TCkKIGlmIG06PVtuW3g6eSsxXWZvciB4IGluIHJhbmdlKEwobikpZm9yIHkgaW4gcmFuZ2UoeCxMKG4pKWlmIGFsbChuW3g6eSsxXWluIGEgZm9yIGEgaW4gcyldOgogIGZvciBxIGluIG06CiAgIGEsYj1bWypmaWx0ZXIoTm9uZSx4KV1mb3IgeCBpbiB6aXAoKltqLnNwbGl0KHEsMSlmb3IgaiBpbiBzXSldO3gseT1bcChhLDEpXWlmIGEgZWxzZVtdLFtwKGIsMSldaWYgYiBlbHNlW107eWllbGQgZnJvbSBQKCooeCtbKHEsKV0reSkpCiAgIGlmIDE+bDp5aWVsZCgqWyh1LClmb3IgdSBpbiBEKGEpXSxxLCpbKHUsKWZvciB1IGluIEQoYildKQogIGlmIDE+bDoKICAgZm9yIGogaW4gdyhzKToKICAgIGlmfi1hbGwoeFswXWZvciB4IGluIGopOnlpZWxkIGZyb20gUCgqW3AoYiwxKWlmIGEgZWxzZVtiXWZvciBhLGIgaW4gal0pCiBlbHNlOnM9W3ggZm9yIHkgaW4gcyBmb3IgeCBpbihbW3ldLHldW2FueShhbnkoaiBpbiB2IGZvciB2IGluIHMgaWYgdiE9eSlmb3IgaiBpbiB5KV0pXTt5aWVsZCBUKFsodSwpZm9yIHUgaW4gc29ydGVkKHNldChzKSxrZXk9cy5pbmRleCldKQpkZWYgZShzKTp5aWVsZCBmcm9tIG1hcCgnJy5qb2luLFAoKltba11pZiBJKGssc3RyKWVsc2VbKmUoayksJyddZm9yIGsgaW4gc10pKQpkZWYgdChzKToKIGZvciBpIGluIHM6CiAgaWYgSShpLHN0cik6eWllbGQgaQogIGVsaWYgYW55KEkoaixzdHIpZm9yIGogaW4gaSk6eWllbGQgVCh0KGkpKQogIGVsc2U6eWllbGQgZnJvbSB0KGkpCmRlZiBmKHMpOnM9cy5zcGxpdCgnLCAnKTtyZXR1cm4gbWluKFsoKHY6PVQodChpKSkpLHN1bSh+LShqIGluIHMpZm9yIGogaW4gZSh2KSkpZm9yIGkgaW4gc2V0KHAocykpXSxrZXk9bGFtYmRhIHg6eFsxXSkKCiNtYWluIHRlc3QgY2FzZXMKcHJpbnQoZigndGhlaXInKSkKcHJpbnQoZigndGhlaXIsIGhlcicpKQpwcmludChmKCdoZXIsIGhpbScpKQpwcmludChmKCdzaGUsIGhlJykpCnByaW50KGYoJ3RoZXksIHNoZSwgaGUnKSkKcHJpbnQoZigndGhlbSwgaGVyLCBoaW0nKSkKcHJpbnQoZignZ29jYSwgb2MsIG9jYScpKQpwcmludChmKCdnb2NhLCBzb2NhLCBvYywgZ29jZSwgc29jZScpKQpwcmludChmKCdnb2NhLCBzb2NhLCBnc29jYWUsIGdvY2UsIHNvY2UnKSkKcHJpbnQoZignZ29jYSwgc29jYSwgZ3N4b2NhZSwgZ29jZSwgc29jZSwgeG9jZScpKQ==