The code-golfer way of searching a library

Question

Challenge:

I have thousands of songs in my music collection, and luckily for me, my favorite player has a search function. I also have a great memory—I can remember the title of every song in my collection. However, I'm very lazy and don't like to type—each extra keystroke is a chore!

• What is the shortest string I must search for to isolate one song? Help me memorize a list of keys I can use to minimize typing when searching!

This is code-golf, so shortest code wins.

---

Rules:

Given an input list of song titles, generate a list of search keys subject to the following constraints:

1. Each song title should have a search key.
2. The total number of characters in the output list must be as few as possible.
3. My favorite music player is foobar2000:
   • The search function is not case-sensitive. (apple is the same as aPpLE).
   • Each search key must consist of one or more "words", in any order, separated by spaces:
     • Each word must be a substring of the corresponding song title.
     • If the same substring is specified multiple times, then it must occur that many times in its corresponding song title.
     • If a substring itself contains a space, then that substring must be surrounded with quotes.

Hints:

• Often, for some song titles, there are multiple search keys meeting rule 2. In such a case, any one key will do, but you get brownie points for listing them all.
• You may assume that the input list will only ASCII characters, but brownie points will be awarded for UTF-8 compatibility.
• Was Rule 3 hard to follow? Here's how it works:

+----------------------+ +--------+ +----------------+ +------------------------------------+
|         Input        | | Output | |   Statistics   | |             Explanation            |
|----------------------| |--------| |----------------| |------------------------------------|
|                      | | Search | |  Key   |  # of | |                                    |
|      Song title      | |  Key   | | length | words | |   Why is the output what it is?    |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanna Be A Wanna Bea | | e e    | |      3 |     2 | |      ["Wanna Be A Wanna Bea"]      |
|                      | |        | |        |       | |   is the only string containing    |
|                      | |        | |        |       | |            ["e"] twice             |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanta Bea A Wanna B  | | t ea   | |      4 |     2 | |       ["Wanta Bea A Wanna B"]      |
|                      | |        | |        |       | | is the only string containing both |
|                      | |        | |        |       | |          ["t"] and ["ea"]          |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanta Be A Wanna B   | | t "e " | |      6 |     2 | |       ["Wanta Be A Wanna B"]       |
|                      | |        | |        |       | | is the only string containing both |
|                      | |        | |        |       | | ["t"] and ['e' preceding a space]  |
+----------------------+ +--------+ +----------------+ +------------------------------------+

Total number of characters in output (par): 13

---

Example:

If my music collection consisted only of two albums, Michael Jackson's Off the Wall and Thriler:

+--------------------------------+ +--------+ +----------------+
|             Input              | | Output | |   Statistics   |
|--------------------------------| |--------| |----------------|
|                                | | Search | |  key   | # of  |
|           Song title           | |  key   | | length | words |
|--------------------------------| |--------| |--------+-------|
| Don't Stop 'Til You Get Enough | | Do     | |      2 |     1 |
| Rock with You                  | | Ro     | |      2 |     1 |
| Working Day and Night          | | Wo     | |      2 |     1 |
| Get on the Floor               | | Fl     | |      2 |     1 |
| Off the Wall                   | | ff     | |      2 |     1 |
| Girlfriend                     | | lf     | |      2 |     1 |
| She's out of My Life           | | Sh     | |      2 |     1 |
| I Can't Help It                | | Ca     | |      2 |     1 |
| It's the Falling in Love       | | v      | |      1 |     1 |
| Burn This Disco Out            | | Bu     | |      2 |     1 |
| Wanna Be Startin' Somethin'    | | nn     | |      2 |     1 |
| Baby Be Mine                   | | Ba     | |      2 |     1 |
| The Girl Is Mine               | | G M    | |      3 |     2 |
| Thriller                       | | hr     | |      2 |     1 |
| Beat It                        | | Bea    | |      3 |     1 |
| Billie Jean                    | | J      | |      1 |     1 |
| Human Nature                   | | Hu     | |      2 |     1 |
| P.Y.T. (Pretty Young Thing)    | | .      | |      1 |     1 |
| The Lady in My Life            | | La     | |      2 |     1 |
+--------------------------------+ +--------+ +----------------+

Total number of characters in output (par): 37

You may use the lists above to test your program. Here is the raw version of the second list:

["Don't Stop 'Til You Get Enough","Rock with You","Working Day and Night","Get on the Floor","Off the Wall","Girlfriend","She's out of My Life","I Can't Help It","It's the Falling in Love","Burn This Disco Out","Wanna Be Startin' Somethin'","Baby Be Mine","The Girl Is Mine","Thriller","Beat It","Billie Jean","Human Nature","P.Y.T. (Pretty Young Thing)"]

Answer 1

Python 2, 556 bytes

Try it online.

-10 bytes, thanks to @Riker, @ovs

Took me couple evenings to make everything works.
Outputs song name, array of search keys and lenght of search keys combined (including spaces and quotes)

import re
S=map(str.lower,input())
T=len
for s in S:
 y=s;n=T(s)
 def R(r,t):
    global n,y
    l=T(' '.join(t))+2*sum(map(lambda x:' 'in x,t))
    if l>n:return
    if(lambda K:T([s for s in S if T(s)-T(reduce(lambda x,y:re.sub(re.escape(y),'',x,1),K,s))==T(''.join(K))])==1)(t)and l<n:y=t;n=l
    u=[(lambda s,n:n and[''.join(y) for y in eval('zip(s%s)'%(''.join(',s[%s:]'%-~x for x in range(n))))]or list(s))(r,i)for i in range(T(r))]
    for i in range(T(r)):
     for j in range(T(r)-i):R(r[j+T(u[i][j]):],t+[u[i][j]])
 R(s,[])
 print[' 'in x and'"%s"'%x or x for x in y]

---

Some explanation:

T=len

Function len() used very often here, so this renaming saves bytes

---

L=lambda s,n:n and[''.join(y) for y in eval('zip(s%s)'%(''.join(',s[%s:]'%-~x for x in range(n))))]or list(s)

Evaluates all possible substrings of string s lenght n.
eval(...) creates command zip(s,s[1:],s[2:],...,s[n:])
It creates substrings of lenght n from every index of s if possible. So for s='budd' and n='2' it will produce bu, ud, dd

---

F=lambda K:len([s for s in S if len(s)-len(reduce(lambda x,y:re.sub(re.escape(y),'',x,1),K,s))==len(''.join(K))])==1

Filter to check if provided keys (K) are for unique song name.
re.sub is requered for multiple identical keys, like ['nn','nn'] in examples.

---

Inner function def R(r,t) is a recursive one to create all possible combinations of substring, that may describe song name.
Every combination is compared with currently shortest one (if there was any) to lower number of created combinations - if it is larger, it won't be accepted as all of it derivatives.
Function uses 2 variable to track state: n for lenght of current shortest key combination and y for combination itself

---

l=T(' '.join(t))+2*sum(map(lambda x:' 'in x,t))

This calculates length of key combination. ' '.join add spaces between keys and 2*sum(...) calculates number of needed quotes for keys with spaces.

---

u=[L(r,i)for i in range(0,T(r))]

Uses first lambda function to get all possible key combination (of every possible length) for current string.

---

Two for cycles to look through all generated keys and pass them individually to the next recursive step. Key place (j) is needed to correctly slice string at the end of it: r[j+T(u[i][j]):].
Slice provides string, that started where current key ends, so there won't be any overlaps.
If place is unknown, equal keys would mess everything up.

---

[' 'in x and'"%s"'%x or x for x in y]

Much longer than just y, but keys with spaces should be surrounded by quotes