List Partitoning

https://binarysearch.com/problems/List-Partitioning

^^ Not leetcode, but the problem was nice.

Question

Given a list of strings strs, containing the strings "red", "green" and "blue", partition the list so that the red come before green, which come before blue.

Constraints

• n ≤ 100,000 where n is the length of strs.

This should be done in \mathcal{O}(n)O(n) time.

Bonus: Can you do it in \mathcal{O}(1)O(1) space? That is, can you do it by only rearranging the list (i.e. without creating any new strings)?

Example 1

Input

strs = ["green", "blue", "red", "red"]

Output

["red", "red", "green", "blue"]

Answer

Start from the beginning swapping in all reds. Picking up where that left off, swap in all greens. All blues are where they need to be.

class Solution:
    def solve(self, s):
        def partition(s, start, word):
            for i in range(start, len(s)):
                if s[i] == word:
                    s[i], s[start] = s[start], s[i]
                    start += 1
            return start

        start = partition(s, 0, "red")
        partition(s, start, "green")
        return s