https://leetcode.com/problems/remove-duplicate-letters

from collections import defaultdict
from typing import Dict, List
 
 
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        if len(s) == 0:
            return ''
 
        letter_positions = self.find_letter_positions(s)
 
        position_letters = dict()
 
        for l, positions in letter_positions.items():
            for p in positions:
                position_letters[p] = l
 
        letters = sorted(set(s))
        result = ''
 
        current_position = 0
 
        while len(letters) > 0:
            i = 0
            is_letter_chosen = False
 
            while i < len(letters):
                l = letters[i]
                positions = [k for k in letter_positions[l] if k >= current_position]
 
                for p in positions:
                    if not self.can_take_letter(l, p, letters, position_letters):
                        continue
 
                    result += l
                    current_position = p
 
                    is_letter_chosen = True
                    letters.remove(l)
 
                    break
 
                if len(letters) == 0:
                    break
 
                if is_letter_chosen:
                    current_position = min(k for k in position_letters if k > p)  # TODO: optimize
 
                    break
 
                i += 1
 
            assert is_letter_chosen
 
        return result
 
    def find_letter_positions(
            self,
            s: str) -> Dict[str, List[int]]:
 
        if len(s) == 0:
            return dict()
 
        result = defaultdict(list)
 
        i = 0
        current_letter = s[0]
 
        result[current_letter].append(0)
 
        i += 1
 
        while i < len(s):
            while i < len(s) and s[i] == current_letter:
                i += 1
 
            if i == len(s):
                break
 
            current_letter = s[i]
            result[current_letter].append(i)
 
        return result
 
    def can_take_letter(
            self,
            letter: str,
            current_position: int,
            letters: List[str],
            position_letters: Dict[int, str]) -> bool:
 
        return (
            set([l for p, l in position_letters.items() if p >= current_position]) >= set(letters)
        )