Redistribute spaces in a fixed-size array of characters

 Redistribute spaces in a fixed-size array of characters

I was given this problem during a g00gle interview last year (hint hint). I didn't pass that round, but I recently coded up my solution and was wondering if this is right, or if there's a better solution? Thanks!

Question:

Input: fixed-size array of characters, containing:

• 0 or more leading spaces
• 0 or more words separated by 1 or more spaces
• 0 or more trailing spaces

Output: the same array where spaces are re-distributed between the words in such a way that they are:

• no more leading spaces
• no more trailing spaces
• roughly the same space gaps between the words. I.e. the minimum and the maximum number of spaces between the words can not differ by more than 1.

Restriction: in-place algorithm. Do not use additional space for copying the characters.

Example:

• Input: "....word1.....word2.....word3....."
• Output: "word1.........word2..........word3"
• Gaps: 10 and 9

My solution: (I do notice that since string is immutable in python, my solution is not in-place?)

# remove leading and trailing spaces
s = raw_input()
orig_len = len(s)
s = s.strip(" ")
new_len = len(s)

# find indices of non-space chars
indices = [i for i in range(new_len) if s[i] != ' ']
num_spaces = orig_len - len(indices)

# find indices of start and end of words
start_indices = [indices[i] for i in range(1, len(indices)) if indices[i] != (indices[i-1] + 1)]
start_indices = [0] + start_indices

end_indices = [indices[i] for i in range(len(indices)-1) if indices[i+1] != (indices[i] + 1)]
end_indices = end_indices + [indices[-1]]

intervals = zip(start_indices, end_indices)
num_words = len(intervals)

spaces_each = num_spaces / (num_words - 1)
extra = num_spaces % (num_words - 1)
adjust = 0

for i in range(num_words-1):
    end_of_prev = intervals[i][1]
    start_of_next = intervals[i+1][0]
    gap = start_of_next - end_of_prev - 1

    if extra > 0:
        if gap != spaces_each + 1:
            s = s[:end_of_prev+1+adjust] + (spaces_each + 1) * ' ' + s[start_of_next+adjust:]
            adjust = adjust + spaces_each + 1 - gap
        extra = extra - 1