The problem is that Python Unicode strings are indexable with integers. They support random access. Each element contains one character, not one byte. The implementation chosen for Python 3 is to handle them as arrays of 1, 2, or 4-byte items, automatically expanding the characters based on the widest character in the string. In Python 2, the options were to build the environment for 2 byte or 4 byte Unicode characters.

This could have been done differently. I would have been tempted to store strings as UTF-8 in Python 3, but hide this from the user. Most of the string functions, including regular expressions, don't really random access a string; they're sequential and forward only. They could work on UTF-8. The ones that return a string index should return an opaque type (say, "StringPos") which has a reference to the string and a position in it. The string functions should accept that type as an index.

If someone applies "int()" to a string index, or performs arithmetic on it, or indexes a string with an actual integer, then it's necessary to scan the entire UTF-8 string and create an index of where each Unicode character starts. This should be a rare event. Especially if there's support for adding or subtracting small integers from a StringPos by walking the string forwards or backwards, rather than building the full index.

Examples:

   s = "This is a test" # Unicode string, internal represention UTF-8
   i = s.find("is")     # returns a StringPos, not an int.
                        # no need to index the string for any of these
   s1 = s[i]            # StringPos selects the char found by find
   s2 = s[i:]           # No need to build an index for this
   s3 = s[i+1:]         # Adding a small int just walks the string
                        # these force generation of an index 
                        # the first operation like this on a string is expensive
                        # comparable to a UTF-8 to rune array conversion
   j = int(i)           # converts a StringPos to an int 
   s4 = s[i*2]          # again, expensive

In practice, those expensive operations are rare.

This would cut Python memory consumption way down when processing mostly-ASCII Unicode data. It would also make it more efficient to input and output UTF-8, which is usually what you want.