Golfing Python string literals

Question

Background

Python 3 has many types of string literals. For example, the string this 'is' an exa\\m/ple can be represented as:

'this \'is\' an exa\\\\m/ple'
"this 'is' an exa\\\\m/ple"
r"this 'is' an exa\\m/ple"
'''this 'is' an exa\\\\m/ple'''
"""this 'is' an exa\\\\m/ple"""
r'''this 'is' an exa\\m/ple'''
r"""this 'is' an exa\\m/ple"""

As you can see, using different delimiters for strings can lengthen or shorten strings by changing the escaping needed for certain characters. Some delimiters can't be used for all strings: r' is missing above (see later for explanation). Knowing your strings is very useful in code golf.

One can also combine multiple string literals into one:

'this \'is\' an ''''exa\\\\m/ple'''
"this 'is' an "r'exa\\m/ple'

---

Challenge

The challenge is, given a printable ASCII string, to output its shortest literal representation in Python.

Details on string mechanics

Strings can be delimited using ', ", ''' and """. A string ends when the starting delimiter is hit again unescaped.

If a string literal starts with ''' or """ it is consumed as the delimiter. Otherwise ' or " is used.

Characters can be escaped by placing a \ before them. This inserts the character in the string and eliminates any special meaning it may have. For example, in 'a \' b' the middle ' is escaped and thus doesn't end the literal, and the resulting string is a ' b.

Optionally, one of r or R may be inserted before the starting delimiter. If this is done, the escaping \ will appear in the result. For example, r'a \' b' evaluates to a \' b. This is why a ' b cannot be delimited by r'.

To escape ''' or """, one only needs to escape one of the characters.

These literals can be concatenated together, which concatenates their contents.

Rules

• The input is the string to golf. Printable ASCII only, so no newlines or other special characters.
• The output is the golfed string literal. If there are multiple solutions, output one.
• To simplify the challenge, in non-r strings any escapes except for \\, \' and \" are considered invalid. They must not be used in the output, even though '\m' is equal to '\\m' in Python. This removes the need to process special escape codes such as \n.
• Builtins for golfing Python strings are disallowed. Python's repr is allowed, since it's crappy anyway.
• Standard code-golf rules apply.

Example inputs/outputs

I tried my best to verify these, but let me know if there are mistakes. If there are multiple valid outputs to the cases, they are all listed below the input.

test
 -> 'test'
 -> "test"
te\st
 -> 'te\\st'
 -> "te\\st"
 -> r'te\st'
 -> r"te\st"
te'st
 -> "te'st"
te"st
 -> 'te"st'
t"e"s't
 -> 't"e"s\'t'
te\'st
 -> "te\\'st"
 -> r'te\'st'
 -> r"te\'st"
te\'\"st
 -> r'te\'\"st'
 -> r"te\'\"st"
t"'e"'s"'t"'s"'t"'r"'i"'n"'g
 -> """t"'e"'s"'t"'s"'t"'r"'i"'n"'g"""
 -> '''t"'e"'s"'t"'s"'t"'r"'i"'n"'g'''
t"\e"\s"\t"\s'\t"\r"\i"\n"\g
 -> r"""t"\e"\s"\t"\s'\t"\r"\i"\n"\g"""
 -> r'''t"\e"\s"\t"\s'\t"\r"\i"\n"\g'''
t"""e"""s"""'''t'''s'''"""t"""r"""'''i'''n'''g
 -> 't"""e"""s"""'"'''t'''s'''"'"""t"""r"""'"'''i'''n'''g"
t\"""e\"""s\"""'''t'''s'''\"""t\"""r\"""'''i'''n'''g
 -> r"""t\"""e\"""s\"""'''t'''s'''\"""t\"""r\"""'''i'''n'''g"""
t"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'\
 -> r't"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'''\\'
 -> r't"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\''"\\"
"""t"'e"'s"'t"'s"'t"'r"'i"'n"'g'''
 -> """\"""t"'e"'s"'t"'s"'t"'r"'i"'n"'g'''"""
 -> '''"""t"'e"'s"'t"'s"'t"'r"'i"'n"'g''\''''

Thanks to Anders Kaseorg for these additional cases:

\\'"\\'\
 -> "\\\\'\"\\\\'\\"
''"""''"""''
 -> '''''"""''"""'\''''

Answer 1

Python 3, 264 262 bytes

f=lambda s,b='\\',r=str.replace:min(sum([['r'+d+s+d,d+r(r(s[:-1],b,b+b),d,d[1:]+b+d[0])+b*(s[-1:]in[b,d[0]])+s[-1:]+d][d in r(r(s+d[1:],b+b,'x'),b+d[0],b)or r(s,b+b,'')[-1:]==b:]for d in["'",'"',"'''",'"""']],[f(s[:k])+f(s[k:])for k in range(1,len(s))]),key=len)

Try it online!

This works but is very slow without memoization, which you can add with

import functools
f=functools.lru_cache(None)(f)

It found an improved solution for one of the test cases:

t"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'\
 -> 't"e"s"t"s"t"r"i"n"g"'r"\'\'\'\'\'\'\'"'\\'
 -> r't"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'''\\'

Previous versions of this answer returned incorrect results on the following, which could be added as test cases:

\\'"\\'\
 -> "\\\\'\"\\\\'\\"
''"""''"""''
 -> '''''"""''"""'\''''