Problem statement

https://binarysearch.com/problems/Sentence-Reversal/

Solution

Equal to Leetcode 0151. Reverse Words in a String.

Complexity

It is O(n) for time and almost O(1) for space: you need to reverse parts of string in place, instead of using [::-1].

Code

class Solution:
    def solve(self, chars):
        slow, n = 0, len(chars)
        for fast in range(n):
            if chars[fast] != " " or (fast > 0 and chars[fast] == " " and chars[fast-1] != " "):
                chars[slow] = chars[fast]
                slow += 1
                
        if slow == 0: return ""       
        chars = chars[:slow-1] if chars[-1] == " " else chars[:slow]
        chars.reverse()
        
        slow, m = 0, len(chars)
        for fast in range(m + 1):
            if fast == m or chars[fast] == " ":
                chars[slow:fast] = chars[slow:fast][::-1]
                slow = fast + 1
                
        return chars